day 40 动态规划

LeetCode 188 买卖股票的最佳时机IV

最多能买卖股票k此，所以就会有2k个状态。

classSolution{publicintmaxProfit(intk,int[]prices){int[][]dp=newint[prices.length][2*k+1];for(intj=1;j<2*k;j+=2){dp[0][j]=-prices[0];}for(inti=1;i<prices.length;i++){dp[i][0]=dp[i-1][0];for(intj=0;j<2*k;j+=2){dp[i][j+1]=Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i]);dp[i][j+2]=Math.max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);}}returndp[prices.length-1][2*k];}}

LeetCode 309 最佳买卖股票时机含冷冻期

分为四个状态，dp[0]持股，dp[1]一直不持股，dp[2]当天就卖出股票状态，dp[3]达到冷冻期。

classSolution{publicintmaxProfit(int[]prices){if(prices==null||prices.length==0){return0;}int[][]dp=newint[prices.length][4];dp[0][0]=-prices[0];dp[0][1]=0;dp[0][2]=0;dp[0][3]=0;for(inti=1;i<prices.length;i++){dp[i][0]=Math.max(dp[i-1][0],Math.max(dp[i-1][1]-prices[i],dp[i-1][3]-prices[i]));dp[i][1]=Math.max(dp[i-1][1],dp[i-1][3]);dp[i][2]=dp[i-1][0]+prices[i];dp[i][3]=dp[i-1][2];}returnMath.max(dp[prices.length-1][1],Math.max(dp[prices.length-1][2],dp[prices.length-1][3]));}}

LeetCode 714 买卖股票的最佳时机含手续费

多减去一次手续费就可以。

classSolution{publicintmaxProfit(int[]prices,intfee){int[][]dp=newint[prices.length][2];dp[0][0]=0;dp[0][1]=-prices[0];for(inti=1;i<prices.length;i++){dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);}returndp[prices.length-1][0];}}