动态规划 —— dp 问题-买卖股票的最佳时机IV

前言

在开始之前先说一下本题与 买卖股票的最佳时机Ill 的解法很相似，也可以去参考lll

  

动态规划 —— dp 问题-买卖股票的最佳时机III-CSDN博客https://blog.csdn.net/hedhjd/article/details/143671809?spm=1001.2014.3001.5501

1. 买卖股票的最佳时机IV

题目链接：

188. 买卖股票的最佳时机 IV - 力扣（LeetCode）https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/

2. 题目解析  

3. 算法原理

状态表示：以某一个位置为结尾或者以某一个位置为起点

  

  

dp[i]表示：第i天结束之后，此时的最大利润 ：两种情况：

  

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

  

2. g[i][j]表示：第i天结束之后，完成了j次交易，处于卖出状态，此时的最大利润

2. 状态转移方程

  

在第i-1天处于买入状态，看买入状态能不能到自己，看卖出状态能不能到买入状态，另一个状态也是如此，一共4种状态

  

	买入状态到	卖出状态到
买入状态	什么都不干	-prices[i](买股票)
卖出状态	+prices[i](交易次数+1)	什么都不干

1. f[i][j] = max(f[i-1][j] , g[i-1][j] - prices[i])

  

2. g[i][j] = max(g[i-1][j] , f[i-1][j-1] + prices[i]

  

  

3. 初始化 ：把dp表填满不越界，让后面的填表可以顺利进行

  

本题的初始化与买卖股票的最佳时机Ill相同，就不多做解释了（不理解可以去看，有详细解释），直接写出来，直接将第二个状态转移方程修改为：

                                1. g[i][j] = g[i-1][j]（此状态一定不会越界）

   

                                 2. if(j-1>=0)     g[i][j] = max(g[i][j] , f[i-1][j-1] + prices[i]
 

  

本题初始化就是先将表里的所有值都初始化为-无穷大，再把f[0][0] = --prices[0],g[0][0] = 0 

4. 填表顺序 

  

本题的填表顺序是：从上往下填写每一行，每一行从左往右，两个表同时填

5. 返回值 ：题目要求 + 状态表示     

  

因为是要最大利润，所以买入状态不用考虑  

本题的返回值是：g表里最后一行里面的最大值

4. 代码 

动态规划的固定四步骤：1.  创建一个dp表

                                        2. 在填表之前初始化

                                        3. 填表（填表方法：状态转移方程）

                                        4. 确定返回值

#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        const int INF = 0x3f3f3f3f;//将无穷大赋予给INF

        int n = prices.size();
        //处理一下细节问题
        k = min(k, n / 2);
        //1.  创建dp表
        vector<vector<int>>f(n, vector<int>(k + 1, -INF));
        auto g = f;

        //2. 在填表之前初始化
        f[0][0] = -prices[0];
        g[0][0] = 0;

        //3. 填表（填表方法：状态转移方程）
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j <= k; j++)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - 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]);
            }
        }
        //g表里最后一行里面的最大值
        int ret = 0;
        for (int j = 0; j <= k; j++)
            ret = max(ret, g[n - 1][j]);
        return ret;

    }
};

完结撒花~