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

【学会动态规划】买卖股票的最佳时机 IV（18）

news 2025/7/4 7:48:02

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

题目链接：188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

这道题跟上一道题是一模一样啊，我的评价是，当一个 CV 工程师，

我马上 CV 出结果：

上一题的代码：

这一题的代码：

虽然话是这么说，我们还是再做一遍这道题：

2. 算法原理

1. 状态表示

dp[ i ] 表示到第 i 天的时候，所能获得的最大利润，

实际上，我们还是可以将他分成两种情况：

买入状态和可交易状态，而且我们需要记录完成了几次交易

f [ i ][ j ] 表示第 i 天结束之后，完成了 j 次交易，处于 “买入” 状态的最大利润，

g [ i ][ j ] 表示第 i 天结束之后，完成了 j 次交易，处于 “可交易” 状态的最大利润，

这里再次说明，买入状态指的是手里有股票，

而可交易状态表示的是手里没有股票。

2. 状态转移方程

我们先从 f [ i ][ j ] 开始分析，就两种情况，一种是昨天是买入，一种是昨天是可交易状态，

买入状态啥也不干就行，可交易状态只要在今天买入就能进入买入状态，所以：

f [ i ][ j ] = max( f [ i - 1 ][ j ]，g [ i - 1 ][ j ] - p [ i ] )

然后是 g [ i ][ j ] ，也是同样的两种情况，

如果是买入状态就卖出，当天的 j 是比现在小1的，如果是可交易状态，就啥也不干就行，所以：

g [ i ][ j ] = max( g[ i - 1 ][ j ]，f [ i - 1 ][ j - 1 ] + p [ i ] )

3. 初始化

为了防止越界，我们需要对他进行一些特殊的处理，

然后为了防止前面的值影响后面的值，我们需要把数组内容初始化成负无穷大

然后把 f [ 0 ][ 0 ] = -p[ 0 ]，让 g [ 0 ][ 0 ] = 0 即可

4. 填表顺序

从上往下，从左往右，两个表一起填

5. 返回值

g 表最后一行的最大值

3. 代码编写

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();vector<vector<int>> f(n, vector<int>(k + 1, -0x3f3f3f3f));auto g = f;f[0][0] = -prices[0], g[0][0] = 0;for(int i = 1; i < n; i++) {for(int j = 0; j < k + 1; j++) {f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);g[i][j] = g[i - 1][j];if(j > 0) g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);}}int ans = 0;for(auto e : g[n - 1]) ans = max(ans, e);return ans;}
};