Leetcode面试经典150题-188.买卖股票的最佳时机IV

本文主要是介绍Leetcode面试经典150题-188.买卖股票的最佳时机IV，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解法都在代码里，不懂就留言或者私信，这个稍微难点，我提供了两种解法

/**基本的动态规划求解的过程 */public static int maxProfit2(int k, int[] prices) {/**题目给的数组不会为null，这里习惯性的健壮性判断如果交易日小于2，不可能获得任何的利润 */if(prices == null || prices.length < 2) {return 0;}/**思路分析：本题只限制了一个交易数量，我们可以原地买卖，也就是说如果还没有凑够k的话，我们可以当天当天卖虽然这没有任何的意义，我们使用动态规划求解:dp数组的含义是dp[i][j]代表在0~i上做j次交易可以获得最大利润i的变化范围0~prices.length-1，j的变化范围0~k有一点需要注意:如果k大于prices.length/2，那就可以无限次买卖了，那就是题目2https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii毕竟我们的动态规划时间复杂度比较高，所以能不用还是不用了*/if(k >= prices.length / 2) {int max = 0;for(int i = 1; i < prices.length; i++) {max += Math.max(0, prices[i]-prices[i-1]);}return max;} else {int[][] dp = new int[prices.length][k+1];/**根据dp数组含义，最后我们要的是0~prices.length-1上做k次交易所能获得的最大利润*//**我们先初始化第一行，也就是在0~0上做0~k次交易，同一天买同一天卖不可能有任何利润*/for(int j = 0; j <= k; j++) {dp[0][j] = 0;}/**第一列也可以先初始化了，也就是0~i上不做交易，不做交易当然是0了,其实int默认是0，第一行和第一列都不用初始化这样写看起来比较清晰*/for(int i = 0; i < prices.length; i++) {dp[i][0] = 0;}/**对于一般的情况，i和j的下标都从1开始 */for(int i = 1; i < prices.length; i++) {for(int j = 1; j <= k; j++) {/**0~i上做j次交易有两种情况：1.前面0~i-1已经做了j次交易，这里直接等于dp[i-1][j]*/int p1 = dp[i-1][j];/**第二种情况；前面0~0，0~1...0~i-1做了j-1次交易，然后前面最后一次交易的那天买入，当前卖出 */int p2 = 0;for(int pre = 0; pre < i; pre ++) {p2 = Math.max(p2, dp[pre][j-1] + prices[i] - prices[pre]);}dp[i][j] = Math.max(p1, p2);}}return dp[prices.length - 1][k];}}/**动态规划+斜率优化的解法，最优解*/public static int maxProfit(int k, int[] prices) {/**题目给的数组不会为null，这里习惯性的健壮性判断如果交易日小于2，不可能获得任何的利润 */if(prices == null || prices.length < 2) {return 0;}/**思路分析：本题只限制了一个交易数量，我们可以原地买卖，也就是说如果还没有凑够k的话，我们可以当天当天卖虽然这没有任何的意义，我们使用动态规划求解:dp数组的含义是dp[i][j]代表在0~i上做j次交易可以获得最大利润i的变化范围0~prices.length-1，j的变化范围0~k有一点需要注意:如果k大于prices.length/2，那就可以无限次买卖了，那就是题目2https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii毕竟我们的动态规划时间复杂度比较高，所以能不用还是不用了*/if(k > prices.length) {int max = 0;for(int i = 1; i < prices.length; i++) {max += Math.max(0, prices[i]-prices[i-1]);}return max;} else {int[][] dp = new int[prices.length][k+1];/**根据dp数组含义，最后我们要的是0~prices.length-1上做k次交易所能获得的最大利润*//**我们先初始化第一行，也就是在0~0上做0~k次交易，同一天买同一天卖不可能有任何利润*/for(int j = 0; j <= k; j++) {dp[0][j] = 0;}/**第一列也可以先初始化了，也就是0~i上不做交易，不做交易当然是0了,其实int默认是0，第一行和第一列都不用初始化这样写看起来比较清晰*/for(int i = 0; i < prices.length; i++) {dp[i][0] = 0;}/**对于一般的情况，i和j的下标都从1开始 */for(int j = 1; j <= k; j++) {int preMax = 0;for(int i = 1; i < prices.length; i++) {/**0~i上做j次交易有两种情况：1.前面0~i-1已经做了j次交易，这里直接等于dp[i-1][j]，和基本动态规划相比，p1没变*/int p1 = dp[i-1][j];/**第二种情况；前面0~0，0~1...0~i-1做了j-1次交易，然后前面最后一次交易的那天买入，当前卖出普通动态规划的解法我们有个枚举的过程，这里使用斜率优化给它省略了dp[2][3]=Math.max(dp[0][2] + prices[2]-prices[0], dp[1][2]+price[2]-prices[1],dp[2][2]+price[2]-prices[2])dp[3][3]=Math.max(dp[0][2] + prices[3]-prices[0], Math.max(dp[1][2]+price[3]-prices[1])), dp[2][2]+price[3]-prices[2])),dp[3][2]+prices[3]-prices[3])这里我们可以发现的规律是dp[0][2]-prices[0]和dp[1][2]-prices[1]对于dp[2][3]和dp[3][3]都有而dp[3][3]多出了dp[3][2]+prices[3]-prices[3]这一项(就是dp[3][2])所以如果我们算dp[2][3]的时候知道dp[0][2]-prices[0]和dp[1][2]-prices[1]谁比较大，算dp[3][3]的时候直接用这个结果就行那这个结果存在哪里了呢？dp[2][3]是这两个值的最大值+prices[2]算出来的，那这个值不就是dp[2][3]-prices[2]吗所以我们可以得到的是dp[3][3]=Math.max(dp[2][3]-prices[2] +prices[3], dp[3][2])抽象成一般位置dp[i][j]=Math.max(dp[i-1][j]-prices[i-1]+prices[i], dp[i][j-1])这个其实也可以写成max(dp[i-1][j]-price[i-1],dp[i][j-1]-prices[i]) + prices[i]前面的部分max(dp[i-1][j]-price[i-1],dp[i][j-1]-prices[i])我们叫它preMax正常这么处理是没有什么问题的这里举个特殊的例子，dp[2][1] = dp[0][0]+prices[2]-prices[0]  dp[1][0]+ prices[2]-prices[1] dp[2][0]dp[1][1] = dp[0][0]+prices[1]-prices[0] dp[1][0]+prices[1]-prices[1]dp[2][1] = Math.max(dp[i-1][j]-price[i-1],dp[i][j-1]-prices[i]) + prices[i]但是对于dp[1][1]呢，它能等于max(dp[i-1][j]-price[i-1],dp[i][j-1]-prices[i]) + prices[i]吗肯定不能啊，因为这里dp[0][j]-prices[0]+prices[1]也就是在0～0上交易了1次？然后又减去了prices[1]和prices[0]的差价，这不是交易两次吗*/int p2 = Math.max(i == 1? prices[i]-prices[i-1]: preMax+prices[i], dp[i][j-1]);preMax = p2 - prices[i];dp[i][j] = Math.max(p1, p2);}}return dp[prices.length - 1][k];}}

运行结果