动态规划 —— dp 问题-买卖股票的最佳时机含冷冻期

江河入海，知识涌动，这是我参与江海计划的第5篇。

1. 买卖股票的最佳时机含冷冻期

题目链接：

309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/

2. 题目解析

3.  算法原理

状态表示：以某一个位置为结尾或者以某一个位置为起点

   

dp[i][0]表示：第i天结束之后，处于买入状态，此时的最大利润

  

dp[i][1]表示：第i天结束之后，处于可交易状态，此时的最大利润

   

dp[i][2]表示：第i天结束之后，处于冷冻期状态，此时的最大利润

  

2. 状态转移方程

在第i-1天处于买入状态，看买入状态能不能到自己，看可交易状态能不能到买入状态，看冷冻期状态能不能到买入状态，其他两个状态也是如此，一共9种状态

     

买入状态到 可交易状态到 冷冻期状态到

买入状态

0

什么都不干（yes） -prices[i](买股票) 不能 可交易状态1 不能 什么都不干（yes） 什么都不干（yes） 冷冻期状态2 +prices[i](卖股票) 不能 不能

根据最近的一步来划分问题：

   

1. dp[i][0]=max(dp[i-1][0] , dp[i-1][1] - prices[i]) 

   

2. dp[i][1]=max(dp[i-1][1] , dp[i-1][2]) 

   

3. dp[i][2]=dp[i-1][0]+prices[i]

3. 初始化 ：把dp表填满不越界，让后面的填表可以顺利进行

  

要想处于买入状态就需要进行买入： dp[0][0]=-prices[0]

   

dp[0][1]=0       dp[0][2]=0

4. 填表顺序 

    

本题的填表顺序是：从左往右，三个表同时填（因为填写其中一个表需要用到其他两个表）

5. 返回值 ：题目要求 + 状态表示    

    

因为是要最大利润，所以买入状态不用考虑  

本题的返回值是：max(dp[n-1][1],dp[n-1][2])

4. 代码 

动态规划的固定四步骤：1.  创建一个dp表

                                        2. 在填表之前初始化

                                        3. 填表（填表方法：状态转移方程）

                                        4. 确定返回值

class Solution {public: int maxProfit(vector& prices) { int n = prices.size(); //1. 创建一个规模(n*3)的dp表 vector<vector>dp(n, vector(3));        //2. 在填表之前初始化 dp[0][0]=-prices[0];         //3. 填表（填表方法：状态转移方程） 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]; }        //4. 确定返回值 return max(dp[n-1][1],dp[n-1][2]); }};

未完待续~