《算法题讲解指南：动态规划算法--简单多状态dp问题》--15.买卖股票的最佳时机含冷冻期，16.买卖股票的最佳时期含手续费

🔥小叶-duck：个人主页

❄️个人专栏：《Data-Structure-Learning》《C++入门到进阶&自我学习过程记录》
《算法题讲解指南》--优选算法
《算法题讲解指南》--递归、搜索与回溯算法
《算法题讲解指南》--动态规划算法

✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游

目录

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

题目链接：

题目描述：

题目示例：

解法(动态规划)：

算法思路：

C++算法代码：

算法总结及流程解析：

16.买卖股票的最佳时期含手续费

题目链接：

题目描述：

题目示例：

解法(动态规划)：

算法思路：

C++算法代码：

算法总结及流程解析：

结束语

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

题目链接：

309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）

题目描述：

题目示例：

解法(动态规划)：

算法思路：

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]
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(); vector<int> freezing(n); vector<int> buyable(n); vector<int> salable(n); buyable[0] = freezing[0] = 0, salable[0] = -prices[0]; for(int i = 1; i < n; i++) { buyable[i] = max(buyable[i - 1], freezing[i - 1]); salable[i] = max(buyable[i - 1] - prices[i], salable[i - 1]); freezing[i] = salable[i - 1] + prices[i]; } return max(max(buyable[n - 1], salable[n - 1]), freezing[n - 1]); } };

算法总结及流程解析：

16.买卖股票的最佳时期含手续费

题目链接：

714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）

题目描述：

题目示例：

解法(动态规划)：

算法思路：

1.状态表示：
对于线性dp，我们可以用「经验+题目要求」来定义状态表示：
i.以某个位置为结尾，巴拉巴拉;
ii.以某个位置为起点，巴拉巴拉。
这里我们选择比较常用的方式，以某个位置为结尾，结合题目要求，定义一个状态表示：
由于有「买入」「可交易」两个状态，因此我们可以选择用两个数组，其中：
f[i]表示：第i天结束后，处于「买入」状态，此时的最大利润;
g[i]表示：第i天结束后，处于「卖出」状态，此时的最大利润。

2.状态转移方程：
我们选择在「卖出」的时候，支付这个手续费，那么在「买入」的时候，就不用再考虑手续费的问题。
对于f[i]，我们有两种情况能到达这个状态：
i.在i-1天「持有」股票，第i天啥也不干。此时最大收益为f[i-1];
ii.在i-1天的时候「没有」股票，在第i天买入股票。此时最大收益为g[i-1]- prices[i]) ;
两种情况下应该取最大值，因此f[i]= max(f[i-1]，g[i-1]-prices[i]) 。
对于g[i]，我们也有两种情况能够到达这个状态:
i.在i-1 天「持有」股票，但是在第i天将股票卖出。此时最大收益为:f[i-1] + prices[i] - fee)，记得手续费；
ii.在i-1 天「没有」股票，然后第i 天啥也不干。此时最大收益为：g[i - 1] ;
两种情况下应该取最大值，因此 g[i]= max(g[i-1]，f[i - 1]+ prices[i] - fee) 。

3.初始化：
由于需要用到前面的状态，因此需要初始化第一个位置。
对于f[0]，此时处于「买入」状态，因此f[0]=-prices[0];
对于g[0]，此时处于「没有股票」状态，啥也不干即可获得最大收益，因此g[0]=0

4.填表顺序：
毫无疑问是「从左往右」，但是两个表需要一起填。

5.返回值：
应该返回「卖出」状态下，最后一天的最大值收益:g[n-1]。

C++算法代码：

class Solution { public: int maxProfit(vector<int>& prices, int fee) { int n = prices.size(); vector<int> buyable(n); vector<int> salable(n); buyable[0] = 0, salable[0] = -prices[0]; for(int i = 1; i < n; i++) { buyable[i] = max(buyable[i - 1], salable[i - 1] + prices[i] - fee); salable[i] = max(buyable[i - 1] - prices[i], salable[i - 1]); } return max(buyable[n - 1], salable[n - 1]); } };

算法总结及流程解析：

结束语

到此，15.买卖股票的最佳时机含冷冻期，16.买卖股票的最佳时期含手续费 这两道算法题就讲解完了。买卖股票的最佳时机含冷冻期，通过定义三个状态（买入、可交易、冷冻期）建立状态转移方程。买卖股票的最佳时期含手续费，采用两个状态（买入、卖出）进行动态规划，并选择在卖出时支付手续费。希望大家能有所收获！