买卖股票 IV
本题和之前的买卖股票类似，都是在给定的交易次数内求最大利润。
我们同样可以使用一个二维的dp数组来表示状态。
用 dp[i][j] 表示第 i 天对股票的持有状态为 j 时的最大利润。j 的状态可以表示为：
j = 0：表示不操作j = 1：表示第一次持有股票j = 2：表示第一次卖出股票j = 3：表示第二次持有股票j = 4：表示第二次卖出股票
可以发现除了 j = 0 以外，当 j 为奇数时表示持有股票，为偶数时表示不持有股票。
因为有 k 次交易，所以二维的dp数组的大小可以定义为 2 * k + 1。
1. 确定dp数组以及下标的含义
根据上面的分析，我们可以定义一个二维的dp数组 dp[i][j]
dp[i][j]表示第i天对股票的持有状态为j时的最大利润。
2. 确定递推公式
到达 dp[i][1] （第一次持有股票）的状态有两种情况：
- 第
i天不买入股票，保持原有状态dp[i-1][1]。 - 第
i天买入股票，说明在第i - 1天不持有股票，买入股票后的所持金额为dp[i-1][0] - prices[i]。
在两者中选择最大的：
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);同理到达 dp[i][2] （第一次不持有股票）的状态有两种情况：
- 第
i天不卖出股票，保持原有状态dp[i-1][2]。 - 第
i天卖出股票，说明在第i - 1天持有股票，卖出股票后的所持金额为dp[i-1][1] + prices[i]。
在两者中选择最大的：
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);同理类比以上的状态，我们可以得到其他状态的递推公式：
for (int j = 0; j < 2 * k - 1; j += 2) {
dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}3. 初始化dp数组
我们可以发现 dp[i][j] 的都是由 dp[i-1][j] 和 dp[i-1][j+1] 递推而来，因此我们可以先初始化 dp[0][j]。
第0天没有操作，所以
dp[0][0] = 0。第0天第一次持有股票，即首日就买入股票，所以
dp[0][1] = -prices[0]。第0天第一次不持有股票，即首日就买入卖出，所以
dp[0][2] = 0。第0天第二次持有股票，所以
dp[0][3] = -prices[0]。第0天第二次不持有股票，所以
dp[0][4] = 0。…
所以在这里我们可以当 j 为偶数时，dp[0][j] = 0，当 j 为奇数时，dp[0][j] = -prices[0]。
for (int j = 1; j < 2 * k; j += 2) {
dp[0][j] = -prices[0];
}4. 遍历顺序
我们可以发现 dp[i][j] 的都是由 dp[i-1][j] 和 dp[i-1][j+1] 递推而来，因此遍历顺序是从前往后
5. 整体代码
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if (prices.size() == 0) return 0;
vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0)); // 二维dp数组，大小为2*k+1
for (int j = 1; j < 2 * k; j += 2) { // 初始化dp数组
dp[0][j] = -prices[0];
}
for (int i = 1; i < prices.size(); i++) {
for (int j = 0; j < 2 * k - 1; j += 2) {
dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
}
return dp[prices.size() - 1][2 * k];
}
};最佳买卖股票时机含冷冻期
1. 确定dp数组以及下标的含义
我们可以定义一个二维的dp数组来表示状态。
dp[i][j]第i天状态为j，所剩的最多现金为dp[i][j]。
2. 确定递推公式
具体可以区分出如下四个状态：
- 状态一：持有股票状态（今天买入股票，或者是之前就买入了股票然后没有操作，一直持有）
- 不持有股票状态，这里就有两种卖出股票状态
- 状态二：保持卖出股票的状态（两天前就卖出了股票，度过一天冷冻期。或者是前一天就是卖出股票状态，一直没操作）
- 状态三：今天卖出股票
- 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天
我们可以将 j 状态表示为:
j = 0：状态1j = 1：状态2j = 2：状态3j = 3：状态4
冷冻期的前一天，只能是 「今天卖出股票」状态，如果是 「不持有股票状态」那么就很模糊，因为不一定是 卖出股票的操作。
到达到买入股票状态（状态一）即：
dp[i][0]，有两个具体操作：- 前一天持有股票，保持不变，
dp[i-1][0]。 - 前一天不持有股票，今天买入股票，那么又会有两种情况：
- 前一天是冷冻期（状态四），那么今天买入股票的金额为
dp[i-1][3] - prices[i]。 - 前一天是卖出股票（状态二），那么今天买入股票的金额为
dp[i-1][1] - prices[i]。
- 前一天是冷冻期（状态四），那么今天买入股票的金额为
所以
dp[i][0]的状态转移方程为：dp[i][0] = max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);- 前一天持有股票，保持不变，
到达到卖出股票状态（状态二）即：
dp[i][1]，有两个具体操作：- 前一天就是卖出股票的状态，保持不变，
dp[i-1][1]。 - 前一天是冷冻期（状态四），那么今天卖出股票的金额为
dp[i-1][3]。
所以有：
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);- 前一天就是卖出股票的状态，保持不变，
到达今天卖出股票状态（状态三）即：
dp[i][2]，就只有一个操作：- 前一天一定是持有股票状态（状态一），那么今天卖出股票的金额为
dp[i-1][0] + prices[i]。
所以有：
dp[i][2] = dp[i - 1][0] + prices[i];- 前一天一定是持有股票状态（状态一），那么今天卖出股票的金额为
到达冷冻期状态（状态四）即：
dp[i][3]，就只有一个操作：- 昨天一定是卖出股票状态（状态三），今天冷冻期的金额为
dp[i-1][2]。
所以有：
dp[i][3] = dp[i - 1][2];- 昨天一定是卖出股票状态（状态三），今天冷冻期的金额为
因此我们可以得到状态转移方程：
dp[i][0] = max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
dp[i][2] = dp[i - 1][0] + prices[i];
dp[i][3] = dp[i - 1][2];3. 初始化dp数组
对于第0天的状态，我们可以直接初始化：
- 状态一：
dp[0][0] = -prices[0]，表示第0天买入股票。 - 状态二：
dp[0][1] = 0 - 状态三：
dp[0][2] = 0 - 状态四：
dp[0][3] = 0
4. 遍历顺序
我们可以发现 dp[i][j] 的都是由 dp[i-1][j] 和 dp[i-1][j+1] 递推而来，因此遍历顺序是从前往后
5. 整体代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n == 0) return 0;
vector<vector<int>> dp(n, vector<int>(4, 0));
dp[0][0] -= prices[0]; // 持股票
for (int i = 1; i < n; i++) {
dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
dp[i][2] = dp[i - 1][0] + prices[i];
dp[i][3] = dp[i - 1][2];
}
return max(dp[n - 1][3], max(dp[n - 1][1], dp[n - 1][2]));
}
};