买卖股票的最佳时机III
最多只能完成两笔交易,那么对于每一天的股票可以有5种状态:
- 没有操作
- 第一次持有股票
- 第一次不持有股票
- 第二次持有股票
- 第二次不持有股票
所以设计的 dp 数组应该有5个维度,分别计算可能得到的最大利润。对于如何递推,是类似于昨天的股票问题的。
对于初始化dp数组,第一次持有与不持有与之前都是一样的,dp[0][1] = -prices[0]、dp[0][2] = 0
。第二次持有与不持有在第0天可以看做第一次持有又在当天卖出,这样就出现了第二次的持有与不持有,此时dp[0][3] = -prices[i]、dp[0][4] = 0
。
最终应该返回什么作为最大利润呢?应该返回 dp[i][4]。这个值其实包括了只交易一笔 dp[i][2] 的情况(相当于当天买当天卖完成第二次的持有)。
class Solution{
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(5, 0));
dp[0][1] = -prices[0];
dp[0][3] = -prices[0];
for(int i = 1; i < n; i++) {
dp[i][0] = dp[i - 1][0]; // 其实没有操作这一状态也可以不考虑,因为不会改变始终是0
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
return dp[n - 1][4];
}
};
买卖股票的最佳时机IV
这道题就是上一道题的外推。最多两笔交易时有5种状态,最多k笔交易则应该有 2*k+1 种状态。
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int len = prices.size();
vector<vector<int>> dp(len, vector<int>(2 * k + 1, 0));
for(int j = 1; j < 2 * k; j += 2) {
dp[0][j] = -prices[0]; // 奇数下标是持股状态,所以应该是-prices[0]
}
for(int i = 1; i < len; 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[len - 1][2 * k];
}
};