目录
力扣309. 买卖股票的最佳时机含冷冻期
难度 中等
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1] 输出: 0
提示：
1 <= prices.length <= 50000 <= prices[i] <= 1000
class Solution {
public:
int maxProfit(vector<int>& prices) {
}
};状态机分析
以某个位置为结尾，结合题目要求，定义⼀个状态表示：
由于有买入、可交易、冷冻期三个状态，因此我们可以选择⽤三个数组，其中：
- dp[i][0] 表示：第 i 天结束后，处于买入状态，此时的最大利润；
- dp[i][1] 表示：第 i 天结束后，处于可交易状态，此时的最大利润；
- dp[i][2] 表示：第 i 天结束后，处于冷冻期状态，此时的最大利润。
处于买入状态的时候，持有股票，此时不能买股票，只能继续持有股票，或者卖出股票。处于可交易状态的时候： 如果在冷冻期，不能买入，如果不在冷冻期，才能买入。
三种状态的转换有个名字叫做状态机：（在下面解释这个图）
对于 dp[i][0] 买入状态，有两种情况能到达这个状态：
- 从买入到买入：在 i - 1 天持有股票，此时最大收益应该和 i - 1 天的保持一致： dp[i - 1] [0] ;
- 从可交易到买入：在 i 天买入股票，那我们应该选择 i - 1 天不在冷冻期的时候买入，由于买入需要花钱，所以此时最大收益为： dp[i - 1][1] - prices[i] ;
两种情况应取最大值，因此： dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]) ;
对于 dp[i][1] 可交易状态，有两种情况能到达这个状态：
- 从可交易到可交易：在 i - 1 天的时候，手上没有股票，也不在冷冻期，但是依旧啥也不⼲到第 i 天，此时 对应的状态为 dp[i - 1][1] ;
- 从冷冻期到可交易：在 i - 1 天的时候，已经处于冷冻期，然后啥也不⼲到第 i 天，此时对应的状态为： dp[i - 1][2] ;
两种情况应取最大值，因此： dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]) ;
对于 dp[i][2] 冷冻期，只有一种情况能到达这个状态：
在 i - 1 天的时候，卖出股票。 因此对应的状态转移为： dp[i][2] = dp[i - 1][0] + prices[i] ;
三种状态都会用到前一个位置的值，因此需要初始化每一行的第一个位置：
- dp[0][0] ：此时要想处于买入状态，必须把第⼀天的股票买了，因此 dp[0][0] = - prices[0] ;
- dp[0][1] ：啥也不用干即可，因此 dp[0][1] = 0 ;
- dp[0][2] ：手上没有股票，买⼀下卖⼀下就处于冷冻期，此时收益为 0 ，因此 dp[0][2] = 0 ;
根据状态表示，三个表从左往右一起填。最后返卖出状态下的最大值，因此应该返回 max(dp[n - 1][1], dp[n - 1] [2]) ;
解析代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(3));
dp[0][0] = -prices[0];
for(int i = 1; i < n; ++i)
{ // 注意prices下标映射
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][2]);
dp[i][2] = dp[i-1][0] + prices[i]; // 在 i-1 天的时候，卖出股票
}
return max(dp[n-1][1], dp[n-1][2]);
}
};
