当前位置：首页 > news >正文

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

news 2026/5/31 20:48:54

🔥小叶-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.初始化：
由于需要用到i=0时的状态，因此我们初始化第一行即可。
当处于第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(vector<int>& prices) { if(prices.size() <= 1) { return 0; } vector<vector<int>> buyable(prices.size(), vector<int>(3)); vector<vector<int>> salable(prices.size(), vector<int>(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）

题目描述：

题目示例：

解法(动态规划):

算法思路：

4.填表顺序：
从「上往下填」每一行，每一行「从左往右」，两个表「一起填」。

5.返回值：
返回处于「卖出状态」的最大值，但是我们也「不知道是交易了几次」，因此返回g表最后一行的最大值。

C++算法代码：

class Solution { public: int maxProfit(int k, vector<int>& prices) { if(prices.size() <= 1) { return 0; } int n = prices.size(); vector<vector<int>> buyable(n, vector<int>(k + 1, INT_MIN / 2)); vector<vector<int>> salable(n, vector<int>(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.买卖股票的最佳时机III，18.买卖股票的最佳时机IV 这两道算法题就讲解完了。17题针对最多2次交易的情况，定义了buyable和salable两个状态数组，分别表示持有股票和卖出股票的最大利润。18题则扩展为最多k次交易，通过类似的状态转移方程处理。两题的核心思路都是：1）定义持有/卖出两种状态；2）通过状态转移方程计算每日利润；3）初始化首日状态；4）按天递推计算；5）返回最终最大利润。希望大家能有所收获！

查看全文

http://www.jsqmd.com/news/578485/