一、LeetCode309.最佳买卖股票时机含冷冻期
题目链接/文章讲解/视频讲解:https://programmercarl.com/0309.%E6%9C%80%E4%BD%B3%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E6%97%B6%E6%9C%BA%E5%90%AB%E5%86%B7%E5%86%BB%E6%9C%9F.html
状态:已解决
1.思路
这道题多了一个限制条件:卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。也就是说,卖出股票后的第二天不能再买,那么股票要多出两个状态:首先,由于需要知道某天是否是卖出股票后的第二天,我们需要拆分以前的 “未持有股票” 状态为:当天卖出股票、卖出股票>=2天。其次,要多一个冰冻期状态。
(1)确定dp数组以及下标含义
这道题只是股票状态多了两个,故还是一个二维数组,第一维代表天数,第二维代表股票状态,根据上面的分析,我们知道现在有四个股票状态:
dp[i][0]:第 i 天持有股票
dp[i][1]:第 i 天卖出股票
dp[i][2]:第 i 天处于冷淡期
dp[i][3]:第 i 天已卖出股票超过1天
(2)确定递推公式:
对于dp[i][0],第 i 天持有股票要么第i-1天也持有股票,要么是第 i-1 天卖出股票超过1天或刚好处于冷淡期然后今天重新购入一份。故dp[i][0] = max(dp[i-1][0], max(dp[i-1][3] - prices[i],dp[i-1][2]-prices[i]))。
对于dp[i][1],第 i 天卖出股票必定是第 i-1天能持有股票。故dp[i][1] = dp[i-1][0]+prices[i]。
对于dp[i][2],第 i 天处于冷淡期,那么必定是因为第 i-1天卖出了股票,由于冷淡期买不了也没有什么可卖的,故dp[i][2] = dp[i-1][1]。
对于dp[i][3],第 i 天已卖出股票超过1天,那么第 i-1 天也是已卖出股票很久要么处于冷淡期,故dp[i][3] = max(dp[i-1][3], dp[i-1][2])。
(3)初始化dp数组:
根据递推公式,我们需要初始化:dp[0][0-3]。
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = 0;(无具体含义,根据递推公式确定的)
dp[0][3] = 0;(无具体含义,根据递推公式确定的)
(4)确定遍历顺序:
跟以前一样,依旧是外层从前往后遍历天数。
(5)举例推导dp数组:
以 [1,2,3,0,2] 为例,dp数组如下:
根据前面的分析我们知道卖出状态一定包含最大值所处的状态,但现在状态2、3、4都是卖出状态,因此最后要取三者中的最大值。
2.代码实现
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(),vector<int>(4,0));
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = 0;
dp[0][3] = 0;
for(int i=1;i<prices.size();i++){
dp[i][0] = max(dp[i-1][0], max(dp[i-1][3] - prices[i],dp[i-1][2]-prices[i]));
dp[i][1] = dp[i-1][0] + prices[i];
dp[i][2] = dp[i-1][1];
dp[i][3] = max(dp[i-1][3],dp[i-1][2]);
//cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<" "<<dp[i][3]<<endl;
}
return max(dp[prices.size()-1][1],max(dp[prices.size()-1][2],dp[prices.size()-1][3]));
}
};
时间复杂度:O(n)
空间复杂度:O(4*n)
二、 714.买卖股票的最佳时机含手续费
题目链接/文章讲解/视频讲解:https://programmercarl.com/0714.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA%E5%90%AB%E6%89%8B%E7%BB%AD%E8%B4%B9%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html
状态:已解决
1.思路
相对于动态规划:122.买卖股票的最佳时机II (opens new window),本题只需要在计算卖出操作的时候减去手续费就可以了,代码几乎是一样的。唯一差别在于递推公式部分,因此我们只主要讲解一下递推公式部分。
如果第i天持有股票即dp[1](状态压缩), 那么可以由两个状态推出来
- 第i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:dp[1]
- 第i天买入股票,所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即:dp[0] - prices[i]
所以:dp[i][0] = max(dp[1], dp[0] - prices[i]);
如果第i天不持有股票即dp[0]的情况, 依然可以由两个状态推出来
- 第i-1天就不持有股票,那么就保持现状,所得现金就是昨天不持有股票的所得现金 即:dp[0]
- 第i天卖出股票,所得现金就是按照今天股票价格卖出后所得现金,注意这里需要有手续费了即:dp[1] + prices[i] - fee
所以:dp[i][1] = max(dp[0], dp[1] + prices[i] - fee);
2.代码实现
class Solution {
public:
int maxProfit(vector<int>& prices, int fee) {
vector<int> dp(2,0);
dp[0] = 0;
dp[1] = -prices[0];
for(int i=1;i<prices.size();i++){
dp[0] = max(dp[0],dp[1]+prices[i]-fee);
dp[1] = max(dp[1],dp[0]-prices[i]);
}
return dp[0];
}
};
时间复杂度:O(n)
空间复杂度:O(1)