/* * 188. Best Time to Buy and Sell Stock IV * 2016-6-6 by Mingyang * 这个题目我的做法是设立以为二维dp，T[i][j]i是transaction的数量，j是天数 * 也就是在j天以内完成i次交易的最大值 * T[i][j]=max 1. T[i][j-1]------>第j天根本不交易 * 2. （prices[j]-prices[m])+T[i-1][m] ------所有的最大值 * for m=0,...j-1---也就是在m天完成i-1次交易，最后一次由m买进，j卖出
* 想法是正确的但是就是没有利用dp来记录前面的状态，所以会超时，那么后面会给出正确的解法 */ public int maxProfit(int k, int[] prices) { int len=prices.length; if(prices==null||len==0) return 0; int[][] T=new int[k+1][prices.length]; for(int i=0;i<=k;i++){ T[i][0]=0; } for(int j=0;j<prices.length;j++){ T[0][j]=0; } for(int i=1;i<=k;i++){ for(int j=1;j<prices.length;j++){ int maxVal=0; for(int m=0;m<j;m++){ maxVal=Math.max(maxVal,prices[j]-prices[m]+T[i-1][m]); } T[i][j]=Math.max(T[i][j-1],maxVal); } } return T[k][prices.length-1]; }
更加标准的解法，用了一个tmpMax来保存，如果本轮买进，欠着一些钱，以供下一轮来使用
public int maxProfit(int k, int[] prices) { int len = prices.length; if (k >= len / 2) return quickSolve(prices); int[][] t = new int[k + 1][len]; for (int i = 1; i <= k; i++) { int tmpMax = -prices[0]; for (int j = 1; j < len; j++) { //等于要么第j次没有交易，要么j次交易了，有一个tmpMax的辅助变量就等于前一天买进先欠着的钱 t[i][j] = Math.max(t[i][j - 1], prices[j] + tmpMax); //更新这个辅助函数来表示下一次需要的变量 tmpMax = Math.max(tmpMax, t[i - 1][j - 1] - prices[j]); } } return t[k][len - 1]; } private int quickSolve(int[] prices) { int len = prices.length, profit = 0; for (int i = 1; i < len; i++) // as long as there is a price gap, we gain a profit. if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1]; return profit; }