LeetCode 188 买卖股票的最佳时机|V

1.真的好烦了

看见这个题，就其实是把“买卖股票的最佳时机III”的dp方法的k=2改为题上的k就OK

但是，会报错，超内存

然后，看了题解，

一次交易由买入和卖出构成，至少需要两天。所以说有效的限制 k 应该不超过 n/2，如果超过，就没有约束作用了，相当于 k = +infinity。就是“买卖股票的最佳时机II”的情况 k=+无穷

然后我就拼凑了两种方法在一起，也不知道其他大神怎么来的，但是这个系列把我折磨死了

class Solution { public int maxProfit(int k, int[] prices) { if(prices.length==0) return 0; if(k>prices.length/2){ int out=0; for(int i=1;i<prices.length;i++){ if(prices[i]>prices[i-1]){ out+=prices[i]-prices[i-1]; } } return out; } int[][][] dp = new int[prices.length][k+1][2]; for(int i=0;i<prices.length;i++){ for(int j=1;j<=k;j++){ if(i==0){ dp[i][j][0]=0; dp[i][j][1]=-prices[i]; }else{ dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]); dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]); } } } return dp[prices.length-1][k][0]; } }