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];
}
}运行结果
