《算法题讲解指南：动态规划算法--简单多状态dp问题》--17.买卖股票的最佳时机III，18.买卖股票的最佳时机IV

小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录17.买卖股票的最佳时机III题目链接题目描述题目示例解法(动态规划):算法思路C算法代码算法总结及流程解析18.买卖股票的最佳时机IV题目链接题目描述题目示例解法(动态规划):算法思路C算法代码算法总结及流程解析结束语17.买卖股票的最佳时机III题目链接123. 买卖股票的最佳时机 III - 力扣LeetCode题目描述题目示例解法(动态规划):算法思路1.状态表示对于线性dp我们可以用「经验题目要求」来定义状态表示i.以某个位置为结尾巴拉巴拉ii.以某个位置为起点巴拉巴拉。这里我们选择比较常用的方式以某个位置为结尾结合题目要求定义一个状态表示由于有「买入」「可交易」两个状态因此我们可以选择用两个数组。但是这道题里面还有交易次数的限制因此我们还需要再加上一维用来表示交易次数。其中f[i][j]表示:第i天结束后完成了j次交易处于「买入」状态此时的最大利润;g[i][j]表示:第i 天结束后完成了j次交易处于「卖出」状态此时的最大利润。2.状态转移方程对于f[i][j]我们有两种情况到这个状态i.在i一1天的时候交易了j次处于「买入」状态第i天啥也不干即可。此时最大利润为:f[i-1][j];ii.在i-1天的时候交易了j次处于「卖出」状态第天的时候把股票买了。此时的最大利润为:g[i-1][j] -prices[i]。综上我们要的是「最大利润」因此是两者的最大值:f[i][j] max(f[i -1][j]g[i -1][j] - prices[i])。对于g[i][j]我们也有两种情况可以到达这个状态i.在i1天的时候交易了j次处于「卖出」状态第天啥也不干即可。此时的最大利润为: g[i- 1][j];ii.在i-1天的时候交易了j一1 次处于「买入」状态第i天把股票卖了然后就完成了j比交易。此时的最大利润为:f[i-1][j-1] prices[i]。但是这个状态不一定存在要先判断一下。综上我们要的是最大利润因此状态转移方程为g[i][j] g[i - 1][j];if(j 1) g[i][j] max(g[i][j], f[i - 1][j - 1] prices[i]);3.初始化由于需要用到i0时的状态因此我们初始化第一行即可。当处于第0 天的时候只能处于「买入过一次」的状态此时的收益为-prices[o]因此 f[0][0] -prices[0]。为了取max的时候一些不存在的状态「起不到干扰」的作用我们统统将它们初始化为INT_MIN/2(用INT_MIN在计算过程中会有「溢出」的风险这里INT_MIN折半取足够小即可)4.填表顺序从「上往下填」每一行每一行「从左往右」两个表「一起填」。5.返回值返回处于「卖出状态」的最大值但是我们也「不知道是交易了几次」因此返回g表最后一行的最大值。C算法代码class Solution { public: int maxProfit(vectorint prices) { if(prices.size() 1) { return 0; } vectorvectorint buyable(prices.size(), vectorint(3)); vectorvectorint salable(prices.size(), vectorint(3)); buyable[0][0] 0; buyable[0][1] buyable[0][2] INT_MIN/2; salable[0][0] -prices[0]; salable[0][1] salable[0][2] INT_MIN/2; int n prices.size(); for(int i 1; i n; i) { for(int j 0; j 3; j) { if(j 1) { buyable[i][j] max(buyable[i - 1][j], salable[i - 1][j - 1] prices[i]); } else { buyable[i][j] buyable[i - 1][j]; } salable[i][j] max(buyable[i - 1][j] - prices[i], salable[i - 1][j]); } } return max(max(buyable[n - 1][0], buyable[n - 1][1]), buyable[n - 1][2]); } };算法总结及流程解析18.买卖股票的最佳时机IV题目链接188. 买卖股票的最佳时机 IV - 力扣LeetCode题目描述题目示例解法(动态规划):算法思路1.状态表示对于线性dp我们可以用「经验题目要求」来定义状态表示i.以某个位置为结尾巴拉巴拉ii.以某个位置为起点巴拉巴拉。这里我们选择比较常用的方式以某个位置为结尾结合题目要求定义一个状态表示由于有「买入」「可交易」两个状态因此我们可以选择用两个数组。但是这道题里面还有交易次数的限制因此我们还需要再加上一维用来表示交易次数。其中f[i][j]表示:第i天结束后完成了j次交易处于「买入」状态此时的最大利润;g[i][j]表示:第i 天结束后完成了j次交易处于「卖出」状态此时的最大利润。2.状态转移方程对于f[i][j]我们有两种情况到这个状态i.在i一1天的时候交易了j次处于「买入」状态第i天啥也不干即可。此时最大利润为:f[i-1][j];ii.在i-1天的时候交易了j次处于「卖出」状态第天的时候把股票买了。此时的最大利润为:g[i-1][j] -prices[i]。综上我们要的是「最大利润」因此是两者的最大值:f[i][j] max(f[i -1][j]g[i -1][j] - prices[i])。对于g[i][j]我们也有两种情况可以到达这个状态i.在i1天的时候交易了j次处于「卖出」状态第天啥也不干即可。此时的最大利润为: g[i- 1][j];ii.在i-1天的时候交易了j一1 次处于「买入」状态第i天把股票卖了然后就完成了j比交易。此时的最大利润为:f[i-1][j-1] prices[i]。但是这个状态不一定存在要先判断一下。综上我们要的是最大利润因此状态转移方程为g[i][j] g[i - 1][j];if(j 1) g[i][j] max(g[i][j], f[i - 1][j - 1] prices[i]);如果画⼀个图的话它们之间交易关系如下3.初始化由于需要用到i0时的状态因此我们初始化第一行即可。当处于第0 天的时候只能处于「买入过一次」的状态此时的收益为-prices[o]因此 f[0][0] -prices[0]。为了取max的时候一些不存在的状态「起不到干扰」的作用我们统统将它们初始化为INT_MIN/2(用INT_MIN在计算过程中会有「溢出」的风险这里INT_MIN折半取足够小即可)4.填表顺序从「上往下填」每一行每一行「从左往右」两个表「一起填」。5.返回值返回处于「卖出状态」的最大值但是我们也「不知道是交易了几次」因此返回g表最后一行的最大值。C算法代码class Solution { public: int maxProfit(int k, vectorint prices) { if(prices.size() 1) { return 0; } int n prices.size(); vectorvectorint buyable(n, vectorint(k 1, INT_MIN / 2)); vectorvectorint salable(n, vectorint(k 1, INT_MIN / 2)); buyable[0][0] 0; salable[0][0] -prices[0]; for(int i 1; i n; i) { for(int j 0; j k 1; j) { if(j 1) { buyable[i][j] max(buyable[i - 1][j], salable[i - 1][j - 1] prices[i]); } else { buyable[i][j] buyable[i - 1][j]; } salable[i][j] max(buyable[i - 1][j] - prices[i], salable[i - 1][j]); } } int ret INT_MIN; for(int j 0; j k 1; j) { ret max(ret, buyable[n - 1][j]); } return ret; } };算法总结及流程解析结束语到此17.买卖股票的最佳时机III18.买卖股票的最佳时机IV 这两道算法题就讲解完了。17题针对最多2次交易的情况定义了buyable和salable两个状态数组分别表示持有股票和卖出股票的最大利润。18题则扩展为最多k次交易通过类似的状态转移方程处理。两题的核心思路都是1定义持有/卖出两种状态2通过状态转移方程计算每日利润3初始化首日状态4按天递推计算5返回最终最大利润。希望大家能有所收获