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

这篇具有很好参考价值的文章主要介绍了【学会动态规划】买卖股票的最佳时机 IV（18）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

动态规划怎么学？

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

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

1. 题目解析

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

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

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

我马上 CV 出结果：

上一题的代码：

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

这一题的代码：

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

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

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;
    }
};