123.买卖股票的最佳时机III
思路
相比于122.买卖股票的最佳时机III,这道题多了一道限制，就是买卖次数的限制，我的想法是通过增加一维来实现。文章中给出的方法则更加简单，将各种状态全部列出来，用二维数组就可以实现。
- 数组以及下标含义
dp[i][j]:
j=0:到第i天交易次数为0次时的利润。
j = 1: 买入一次
j = 2: 买卖一次
j = 3: 买入两次
j = 4: 买卖两次
当j = 4时的利润最大，可以理解为每笔操作都至少赚钱，如果不能赚钱，就空买卖一次。 - 递推关系
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i])
- 如果不进行操作，那么跟前一天的情况相同，为dp[i - 1][j]
- 如果进行操作，那么相当于在前一天的上一种情况进行操作。例如：如果要完成买入第二次(j = 3)的操作，那么就要在前一天买卖一次（j = 2）的情况下进行操作
- 初始化
当手中没有股票时，需要买入股票，那么当j = 1和 j = 3的情况下，需要初始化为 -prices[i] - 遍历顺序
按照天数，从前向后进行遍历
实现
点击查看代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i = 1; i < prices.size(); i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}
return dp[prices.size() - 1][1];
}
};
复杂度分析
- 时间复杂度：O(n)，n为prices的大小，即所有的天数。
- 空间复杂度：O(n)
188. 买卖股票的最佳时机 IV
思路
这道题与上一题的思路是一致的，只是增加了状态数量而已，使用循环对状态进行操作即可。
实现
点击查看代码
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int m = 2*k + 1;
vector<vector<int>> dp(prices.size(), vector<int>(m, 0));
for(int i = 0; i < m; i++) {
if(i % 2 == 1) {
dp[0][i] = -prices[0];
}
}
for(int i = 1; i < prices.size(); i++) {
dp[i][0] = 0;
for(int j = 1; j < m; j++) {
if(j % 2 == 1) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
}
else {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
}
}
}
return dp[prices.size() - 1][m - 1];
}
};
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)