1. 题⽬链接：309.最佳买卖股票时机含冷冻期
2. 题⽬描述：
3. 解法（动态规划）：
算法思路：
1. 状态表⽰：
对于线性dp ，我们可以⽤「经验+题⽬要求」来定义状态表⽰：
i. 以某个位置为结尾，巴拉巴拉；
ii. 以某个位置为起点，巴拉巴拉。 这⾥我们选择⽐较常⽤的⽅式，以某个位置为结尾，结合题⽬要求，定义⼀个状态表⽰： 由于有「买⼊」「可交易」「冷冻期」三个状态，因此我们可以选择⽤三个数组，其中：
▪ dp[i][0] 表⽰：第i 天结束后，处于「买⼊」状态，此时的最⼤利润；
▪ dp[i][1] 表⽰：第i 天结束后，处于「可交易」状态，此时的最⼤利润；
▪ dp[i][2] 表⽰：第i 天结束后，处于「冷冻期」状态，此时的最⼤利润。
2. 状态转移⽅程：
我们要谨记规则：
i. 处于「买⼊」状态的时候，我们现在有股票，此时不能买股票，只能继续持有股票，或者卖 出股票；
ii. 处于「卖出」状态的时候：
• 如果「在冷冻期」，不能买⼊；
• 如果「不在冷冻期」，才能买⼊。
◦ 对于dp[i][0] ，我们有「两种情况」能到达这个状态：
i. 在i - 1 天持有股票，此时最⼤收益应该和
i - 1 天的保持⼀致： dp[i - 1] [0] ；
ii. 在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. 在i - 1 天的时候，已经处于冷冻期，然后啥也不⼲到第i 天，此时对应的状态为： dp[i - 1][2] ；
ii. 在i - 1 天的时候，⼿上没有股票，也不在冷冻期，但是依旧啥也不⼲到第i 天，此时 对应的状态为dp[i - 1][1] ；
两种情况应取最⼤值，因此： dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]) 。
◦ 对于dp[1][i] ，我们只有「⼀种情况」能到达这个状态：
i. 在i - 1 天的时候，卖出股票。 因此对应的状态转移为： dp[i][2] = dp[i - 1][0] + prices[i] 。
3. 初始化：
三种状态都会⽤到前⼀个位置的值，因此需要初始化每⼀⾏的第⼀个位置：
dp[0][0] ：此时要想处于「买⼊」状态，必须把第⼀天的股票买了，因此dp[0][0] = - prices[0] ； dp[0][1] ：啥也不⽤⼲即可，因此dp[0][1] = 0 ；
dp[0][2] ：⼿上没有股票，买⼀下卖⼀下就处于冷冻期，此时收益为0 ，因此 dp[0][2] = 0 。
4. 填表顺序：
根据「状态表⽰」，我们要三个表⼀起填，每⼀个表「从左往右」。
5. 返回值：
应该返回「卖出状态」下的最⼤值，因此应该返回max(dp[n - 1][1], dp[n - 1] [2]) 。
C++算法代码：
class Solution
{
public:
int maxProfit(vector<int>& prices)
{
int n=prices.size();
//边界情况
if(n==1)
{
return 0;
}
//建表
vector<vector<int>>dp(n,vector<int>(3,0));
//初始化
//0为买入状态，1为卖出状态，2为冷静期状态
dp[0][0]=-prices[0];
//填表
for(int 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];
}
//返回值
return max(dp[n-1][1],dp[n-1][2]);
}
};Java算法代码：
class Solution
{
public int maxProfit(int[] prices)
{
// 1. 创建 dp 表
// 2. 初始化
// 3. 填表
// 4. 返回值
int n = prices.length;
int[][] dp = new int[n][3];
dp[0][0] = -prices[0];
for (int i = 1; i < n; i++)
{
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);
dp[i][2] = dp[i - 1][0] + prices[i];
}
return Math.max(dp[n - 1][1], dp[n - 1][2]);
}
}