【代码随想录】43
2023年10月26日 - 动态规划10
121. 买卖股票的最佳时机
dp[i][0]
代表第i天不持有股票
dp[i][1]
代表第i天持有股票
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
if (len == 0) return 0;
vector<vector<int>> dp(len, vector<int>(2));
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < len; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = max(dp[i - 1][1], -prices[i]);
}
return dp[len - 1][0]; //最后一天不持有股票肯定比持有股票手头的钱多
}
};
122. 买卖股票的最佳时机 II
区别在于第i天持有股票时,可能是第i - 1不持有,但是之前也可能买卖多次,所以 dp[i - 1][0] - prices[i],代表第i天才买入,但是目前钱不是0而是dp[i - 1][0]
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
if (len == 0) return 0;
vector<vector<int>> dp(len, vector<int>(2));
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < len; 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[len - 1][0]; //最后一天不持有股票肯定比持有股票手头的钱多
}
};