动态规划类问题，只需要依次确定dp数组以及dp[i]的含义、初始状态、状态转移方程，然后进行动态规划即可。
一、买卖股票的最佳时机含冷冻期
1、题目描述：
给定一个整数数组 prices，其中第 prices[i] 表示第 i 天的股票价格。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）：
- 卖出股票后，你无法在第二天买入股票（即冷冻期为 1 天）
- 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
2、使用状态机DP，定义三种状态：
dp0：不持股，非冷冻期dp1：持股dp2：冷冻期
状态dp0、dp1、dp2之间分别进行状态转移，典型的多种状态互相转移的题型。其中，dp0、dp1、dp2也可以定义为三个数组（索引从1开始），比如dp0[i]表示第i天结束后为“不持股，非冷冻期”状态。但是，你开辟了更多的空间。
3、代码实现：
#define MAX(a, b) (a > b ? a : b)
int maxProfit(int* prices, int pricesSize) {
int dp0 = 0; // 不持股，非冷冻期(第一天结束时)
int dp1 = -prices[0]; // 持股(第一天结束时)
int dp2 = 0; // 冷冻期(第一天结束时)
// 遍历每一天，从前一天进行状态转移
for (int i = 1; i < pricesSize; i++) {
int new_dp0 = MAX(dp0, dp2);
int new_dp1 = MAX(dp0 - prices[i], dp1);
int new_dp2 = dp1 + prices[i];
dp0 = new_dp0;
dp1 = new_dp1;
dp2 = new_dp2;
}
return MAX(dp0, dp2);
}4、状态转移
二、买卖股票的最佳时机含手续费
1、题目描述
给定一个整数数组 prices，其中 prices[i] 表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
2、解题思路
这道题目不含冷冻期，所以少了一个冷冻期的状态。因此，只需要两种状态：
dp0：不持股dp1：持股
3、代码实现
#define MAX(a, b) (a > b ? a : b)
int maxProfit(int* prices, int pricesSize, int fee) {
int dp0 = 0; // 不持股(第一天结束后)
int dp1 = -prices[0]; // 持股(第一天结束后)
for (int i = 1; i < pricesSize; i++) {
int new_dp0 = MAX(dp0, dp1 + prices[i] - fee);
int new_dp1 = MAX(dp1, dp0 - prices[i]);
dp0 = new_dp0;
dp1 = new_dp1;
}
return dp0;
}4、状态转移
三、买卖股票的最佳时机 III
1、题目描述
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
2、解题思路
最开始我的想法是定义一个flag1，fkag2来记录利润的最大值和次大值，动态规划完成后flag1+flag2就是结果。但是我忽略了一个问题，比如第一天我买入了股票，第二天更新了最大值和次大值，第三天更新了最大值，能用最大值和次大值相加表示结果吗？答案是不能的，因为第一天买的股票只能卖一次。
正确思路：定义四次状态的DP，表示第一次和第二次交易的买卖状态：
buy1：第一次买入后的最大收益sell1：第一次卖出后的最大收益buy2：第二次买入后的最大收益sell2：第二次卖出后的最大收益
3、代码实现
#define MAX(a, b) (a > b ? a : b)
int maxProfit(int* prices, int pricesSize) {
// 初始化第一天的状态
int buy1 = -prices[0]; // 第一天买入
int sell1 = 0; // 第一天买入又卖出
int buy2 = -prices[0]; // 第一次卖出后立即买入第二次
int sell2 = 0; // 第二次卖出
for (int i = 1; i < pricesSize; i++) {
// 1. 第一次持有：以前买的 或 今天刚买入
buy1 = MAX(buy1, 0 - prices[i]);
// 2. 第一次不持有：以前卖了 或 今天卖出
sell1 = MAX(sell1, buy1 + prices[i]);
// 3. 第二次持有：以前就持有 或 今天在第一次交易赚钱的基础上买入
buy2 = MAX(buy2, sell1 - prices[i]);
// 4. 第二次不持有：以前就卖了 或 今天卖出
sell2 = MAX(sell2, buy2 + prices[i]);
}
return sell2;
}代码中体现的一个点很重要，就是buy2的状态是依靠sell1的状态转移过来的，因此这样就符合买了两次，还符合买第二次前出售掉第一次的股票！
4、状态转移
四、买卖股票的最佳时机 IV
1、题目描述
给你一个整数数组 prices 和一个整数 k，其中 prices[i] 是某支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔 交易。也就是说，你最多可以买 k 次，卖 k 次。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
2、解题思路
将题目 3 的逻辑推广到 k 次交易，使用数组存储每次交易的买卖状态：
buy[j]：第 j 次买入后的最大收益sell[j]：第 j 次卖出后的最大收益
3、代码实现
#include <stdlib.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int maxProfit(int k, int* prices, int pricesSize) {
int* buy = (int*)malloc(sizeof(int) * (k + 1));
int* sell = (int*)malloc(sizeof(int) * (k + 1));
sell[0] = 0; // 还没开始交易，兜里只有 0 元
// 第一天时所有交易次数后的买/卖后的金额
for (int j = 1; j <= k; j++) {
buy[j] = -prices[0];
sell[j] = 0;
}
for (int i = 1; i < pricesSize; i++) {
for (int j = 1; j <= k; j++) {
// 第 j 次持有：取决于之前就持有或者今天刚买
buy[j] = MAX(buy[j], sell[j - 1] - prices[i]);
// 第 j 次卖出：取决于之前就卖了或者今天刚卖
sell[j] = MAX(sell[j], buy[j] + prices[i]);
}
}
int result = sell[k];
free(buy);
free(sell);
return result;
}4、核心思想
与只能进行两次交易的代码逻辑相同，只不过这里用数组代替了多个变量。用 for 循环遍历 k 次，可以看作是 buy[1], sell[1], buy[2], sell[2], ..., buy[k], sell[k] 的通用化实现。