动态规划 —— dp 问题-买卖股票的最佳时机IV
前言
在开始之前先说一下本题与 买卖股票的最佳时机Ill 的解法很相似，也可以去参考lll
https://blog.csdn.net/hedhjd/article/details/143671809?spm=1001.2014.3001.55011. 买卖股票的最佳时机IV
题目链接：
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;
}
};完结撒花~
原文地址：https://blog.csdn.net/hedhjd/article/details/143700421
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！