309.最佳买卖股票时机含冷冻期（中等）
思路
状态定义
一、很容易想到四种状态：
- a.今天买入；
- b.今天卖出；
- c.昨天卖出，今天处于冷冻期，无法进行操作；
- d.今天不操作，处于持有状态；
显然，a和d可以合并为持有状态，因此本题需要处理三种状态：「当天持有股票」、「当天不持有股票，卖出」、「当天不持有股票，处于冷冻期」。
二、状态表示
使用三个一维数组来表示这三种状态：
have[i]：第 i 天持有股票的最大收益；sell[i]： 第 i 天售出股票的最大收益；freeze[i]：第 i 天为冷冻期的最大收益；
状态转移
-
对于持有状态 have，它可以由两种情况得到：
第一种是「昨天就持有股票，今天不进行任何操作」，所以今天的收益等于昨天持有股票的收益，即
have[i] = have[i-1];；
第二种是「昨天不属于冷冻期，今天选择买入」，所以今天的收益等于冷冻期后的收益扣去今天的股票价格，即have[i] = freeze[i-1]-prices[i];。要使得收益最大化，所以持有状态的收益就是两种情况下的最大收益，即
have[i] = max(have[i-1], freeze[i-1]-prices[i]);。 -
对于卖出状态，它只能由持有状态得到：「昨天持有股票，今天将其售出」，所以收益是昨天持有股票的收益加上今天的股票价格，即：
sell[i] = have[i-1] + prices[i];。 -
对于冷冻期状态，它可以由两种情况得到：
第一种是「昨天售出，进入冷冻期」，所以收益就是昨天售出股票后的收益，即
freeze[i] = sell[i-1];；
第二种是「昨天是冷冻期，不持有任何股票，今天仍然不进行买入操作，所以保持在冷冻期」，那么收益就是昨天冷冻期的收益，即freeze[i] = freeze[i-1];同样地，要使得收益最大化，所以冷冻期的收益就是两种情况下的最大收益，即
freeze[i] = max(sell[i-1], freeze[i-1]);
初始化
have[0] = -prices[0];：第0天要持有股票，那么一定需要选择买入价格为 prices[0] 的股票；sell[0] = 0：第0天要售出，且不持有股票，那么当天一定是买卖同一支股票，收益为 0；freeze[0] = 0：第 0 天处于冷冻期，可以理解为不进行任何操作，即不买不卖，所以收益为 0。
最终的返回结果
最大收益一定是完成交易（即不持有股票） 的情况，所以返回 sell[n-1] 和freeze[n-1] 的最大值 。
易错点
- 这道题可以多次买卖同一股票，因此初始化条件和之前的题目不一样，第 0 天处于 sell 和 freeze 状态也是合法状态，应该设为 0。
- 对于持有状态，包含两种情况，也可以单独考虑，但稍显繁琐。
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() <= 1) return 0;
int n = prices.size();
vector<int> have(n), sell(n), freeze(n);
// 初始化
have[0] = -prices[0];
sell[0] = freeze[0] = 0;
for(int i=1; i<n; ++i){
have[i] = max(have[i-1], freeze[i-1]-prices[i]);
sell[i] = have[i-1] + prices[i];
freeze[i] = max(sell[i-1], freeze[i-1]);
}
return max(sell[n-1], freeze[n-1]);
}
};
