解法都在代码里，不懂就留言或者私信
建议看这个之前先看股票系列的其他问题123.买卖股票的最佳时机III
Leetcode面试经典150题-121.买卖股票的最佳时机-CSDN博客
Leetcode面试经典150题-122.买卖股票的最佳时机II-CSDN博客
Leetcode面试经典150题-188.买卖股票的最佳时机IV-CSDN博客
尤其是122和188题，这个题的解题其实就是一个简单的加工
class Solution {public static int maxProfit(int[] prices) {return maxProfit(2, prices);}/*** 本题比股票问题2多了一个限制：最多交易k次，也就是可能不能像我们之前的那种每次波谷都买，每次波峰都卖的方式* 除非k是大于等于prices.length/2的* @param k 这里的k是交易的对数，也就是买一次卖一次* @param prices* @return*/public static int maxProfit(int k, int[] prices) {if(prices == null || prices.length < 2 || k < 1) {return 0;}int ans = 0;//如果交易数限制大于prices.length/2，那我们还是可以认为这就是无限次的交易//套用股票问题2的解法if(k >= prices.length / 2) {for(int i = 1; i < prices.length; i++) {int curProfit = Math.max(0,prices[i] - prices[i - 1]);ans += curProfit;}return ans;} else {int N = prices.length;//如果小于这个次数的话就需要好好分析一下了，这里我们使用动态规划的从左往右的尝试模型+业务限制进行解题//先定义一个动态规划表,表中dp[i][j]代表从0~i做不超过j次交易可以获得的最大的利润,所以i的变化范围0~N-1,j的变化范围从0到kint[][] dp = new int[N][k+1];//第一行表示从0~0做0~k次交易，都是0，int默认是0，这里忽略初始化//第一列表示从0~0,0~1...0~N分别做0次交易，你都没有做交易，你有啥利润，也都是0，同样忽略初始化过程//从dp[1][1]开始初始化，如果按照一般的方式进行初始化则dp[8][2] 有几种可能性(1)8位置不交易，那这种可能是dp[7][2]//(2)8位置参与交易，那8位置只能卖（因为我们限制0~8进行2次交易，如果你8位置是买的话利润就无法计算到dp[8][2]里了）//那我们可以分别在0~8进行买入，分别是dp[8][1] + prices[8] - prices[8](8位置买入，8位置卖出)//dp[7][1] + prices[8] - prices[7](7位置买入，8位置卖出)....dp[0][1] + prices[8] - prices[1]//也是就说在O(N*k)的基础上我们又加上了枚举行为，时间复杂度变成了O(N^2*k)这个对于leetCode给的数据量来说，不一定能过//这里我们尝试进行斜率优化，斜率优化分析过程参考：https://www.xiaohuazhuo.com/board/658accf232120d0c5d74f794//这里简单描述一下，其实我们dp[8][2]求解过程中可能性2的每一项都加上了price[8]这个数，也就是说比较过程我们可以不计算这个数//在dp[8][1] - [8] dp[7][1] - [7]....dp[0][1] - [0]中取最大值max，然后+[8]就是当前可能性2的最大值//为什么要求这样的最大值呢，因为我们之后的计算过程用的上，现在举一个dp[9][2]的求解过程,可能性1:9位置不交易 =dp[8][2]//9位置交易，那0~9都可以买入,分别是dp[9][1] + [9] - [9](9位置买入，9位置卖出) dp[8][1] + [9] - [8](8位置买入，9位置卖出)// dp[7][1] + prices[9] - prices[7](7位置买入，9位置卖出)....dp[0][1] + prices[9] - prices[1]//这些项里我们又看到了加上了一样的prices[9], 所以比较的时候只需要拿dp[9][1] - [9] dp[8][1] - [8] dp[7][1] - [7]....dp[0][1] - [0]//这些取最大值就可以了，但是这些出了第一项之外，不就是dp[8][2]的时候求的max吗？所以复用dp[9][2]时候的max=Math.max(max, dp[9][1] - [9])//也就是说对于同一列的后面的行只需要多计算一个数（dp[i][j-1] - prices[i]），然后根据前面的max计算就可以了for(int j = 1; j <= k; j++) {//对于同一列，后面的行依赖于前面的行，这里我们定义一下公共的依赖//这里要注意max的初始值不是0，而是dp[0][j] + prices[0]-prices[0] 的中间部分，也就是dp[0][j]-prices[0]int max = dp[0][j]-prices[0];int p1 = 0;for(int i = 1; i < N; i ++) {p1 = dp[i - 1][j];//0//max函数第一个参数就是当前位置要计算的数dp[i][j-1] - prices[i]max = Math.max(dp[i][j - 1] - prices[i], max);//dp[1][0]-dpdp[i][j] = Math.max(p1, max + prices[i]);System.out.println(i+","+ j + "=" + dp[i][j]);}}ans = dp[N-1][k];}return ans;}
}这个题解法回头我和股票问题4综合一下，其实两个题是一样的，面试肯定保过
