问题
传送门：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
给定一个整数数组prices，其中第 prices[i] 表示第 *i* 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票），且卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]示例 2:
输入: prices = [1]
输出: 0思路
动态规划解决此题。稍微复杂的是，每一个阶段有多种状态（买入、冷冻期、卖出等等）。我们划分出三种互不相交的状态：持有股票、无股票且处于冷冻期、无股票且不处于冷冻期，因此设：
dp[i][0]表示第$i$天持有股票的最大利润dp[i][1]表示第$i$天无股票且不处于冷冻期的最大利润dp[i][2]表示第$i$天无股票且处于冷冻期的最大利润
接下来考虑状态转移，分别考虑每一个阶段的三种状态：
- 若第i天持有股票，则第i-1天可能持有股票，也可能无股票且不处于冷冻期（但是第i天买入股票），取最大值即$dp[i][0] = \max \{ dp[i-1][0], dp[i-1][1] - prices[i] \}$
- 若第i天无股票且不处于冷冻期，则第i-1天可能无股票且不处于冷冻期，也可能无股票出于冷冻期（过了一天不再处于冷冻期），取最大值$dp[i][1] = \max \{ dp[i-1][1], dp[i-1][2] \}$
- 若第i天无股票且处于冷冻期，则第i-1天必然卖出了一张股票，即处于持有股票状态，即$dp[i][2] = dp[i-1][0] + prices[i]$
状态转移
综上有
最后，对dp数组进行遍历取最大值即可。
边界情况
事实上，对于初始情况（即dp[0][i], i=0,1,2），显然不可能处于“无股票且处于冷冻期”状态，因此仅考虑i=0、1。
- 若持有股票，那么必然是第1天就买入股票，因此$dp[0][0] = -prices[0]$
- 若无股票，那么必然第1天无任何操作，即$dp[0][1] = 0$
而$dp[0][2]$似乎没有初始化。但是仔细思考就会发现，直接受其影响的实际上就是$dp[1][1]$的计算，因为根据上面的状态转移方程，$dp[1][1]=\max\{ dp[0][1],dp[0][2] \}$，我们只需保证$dp[1][1]$的正确性，便可保证整个状态转移的正确进行。而$dp[0][1]=0$，因此，赋值$dp[0][2]=0$即可，不影响程序正确性。
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
// dp[i][0]持有股票 dp[i][1]无股票，不处于冷冻期 dp[i][2]无股票，处于冷冻期
int dp[5005][3];
int i, n = prices.size();
memset(dp, 0, sizeof(dp));
dp[0][0] = -prices[0], dp[0][1] = dp[0][2] = 0;
for(i=1; i<n; 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][2]);
dp[i][2] = dp[i-1][0] + prices[i];
}
int ans = 0;
for(i=1; i<n; i++) {
ans = max(ans, max(dp[i][0], max(dp[i][1], dp[i][2])));
}
return ans;
}
};
