一、LeetCode309.最佳买卖股票时机含冷冻期
状态：已解决
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.买卖股票的最佳时机含手续费
状态：已解决
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)