小叶-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(vectorint prices) { int n prices.size(); vectorint freezing(n); vectorint buyable(n); vectorint 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]04.填表顺序毫无疑问是「从左往右」但是两个表需要一起填。5.返回值应该返回「卖出」状态下最后一天的最大值收益:g[n-1]。C算法代码class Solution { public: int maxProfit(vectorint prices, int fee) { int n prices.size(); vectorint buyable(n); vectorint 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.买卖股票的最佳时期含手续费 这两道算法题就讲解完了。买卖股票的最佳时机含冷冻期通过定义三个状态买入、可交易、冷冻期建立状态转移方程。买卖股票的最佳时期含手续费采用两个状态买入、卖出进行动态规划并选择在卖出时支付手续费。希望大家能有所收获