前言
在开始之前先说一下本题与 买卖股票的最佳时机Ill 的解法很相似，也可以去参考lll
动态规划 —— dp 问题-买卖股票的最佳时机III-CSDN博客
https://blog.csdn.net/hedhjd/article/details/143671809?spm=1001.2014.3001.5501
1. 买卖股票的最佳时机IV
题目链接：
188. 买卖股票的最佳时机 IV - 力扣（LeetCode）
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;//将无穷大赋予给INFint 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;}
};完结撒花~
