188. 买卖股票的最佳时机 IV - 力扣LeetCode188. 买卖股票的最佳时机 IV - 给你一个整数数组 prices 和一个整数 k 其中 prices[i] 是某支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说你最多可以买 k 次卖 k 次。注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 示例 1输入k 2, prices [2,4,1]输出2解释在第 1 天 (股票价格 2) 的时候买入在第 2 天 (股票价格 4) 的时候卖出这笔交易所能获得利润 4-2 2 。示例 2输入k 2, prices [3,2,6,5,0,3]输出7解释在第 2 天 (股票价格 2) 的时候买入在第 3 天 (股票价格 6) 的时候卖出, 这笔交易所能获得利润 6-2 4 。 随后在第 5 天 (股票价格 0) 的时候买入在第 6 天 (股票价格 3) 的时候卖出, 这笔交易所能获得利润 3-0 3 。 提示 * 1 k 100 * 1 prices.length 1000 * 0 prices[i] 1000https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/题目描述给定一个整数数组p第i个元素p[i]是股票第i天的价格。 最多可以完成k 笔交易一笔交易 一次买入 一次卖出同一时间不能持有多只股票买入前必须先卖掉手里股票。求能获取的最大利润。动态规划思路状态定义fx[i][j]第i天持有股票已经完成j次卖出当前最大利润gx[i][j]第i天不持有股票已经完成j次卖出当前最大利润优化预处理k min(k, n/2)股票一次完整交易至少占用 2 天买一天、卖一天。n天最多能完成n/2笔交易。如果输入 k 很大超过n/2等价于不限交易次数LeetCode122直接把 k 限制为n/2减少 DP 数组大小节省内存与计算时间。其他的和上上一个类似,这里不过多介绍class Solution { public: int maxProfit(int k, vectorint p) { int np.size(); int minjudge-10000000; kmin(k,n/2); coutkendl; vectorvectorintfx(n,vectorint(k1,minjudge)); auto gxfx; fx[0][0]-p[0]; gx[0][0]0; for(int i1;in;i) { for(int j0;jk;j) { fx[i][j]max(fx[i-1][j],gx[i-1][j]-p[i]); gx[i][j]gx[i-1][j]; if(j1) gx[i][j]max(fx[i-1][j-1]p[i],gx[i][j]); } } int ret0; for(int j0;jk;j) { retmax(ret,gx[n-1][j]); } return ret; } };