123. 买卖股票的最佳时机 III

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

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

1.AC代码:

class Solution {public int maxProfit(int[] prices) {int n=prices.length;int[][] dp=new int[n][5];dp[0][1]=-prices[0];dp[0][3]=-prices[0];for(int i=1;i<n;i++){// 第一次买入dp[i][1]=Math.max(dp[i-1][1],-prices[i]);// 第一次卖出dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);// 第二次买入dp[i][3]=Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);// 第二次卖出dp[i][4]=Math.max(dp[i-1][4],dp[i-1][3]+prices[i]);}return dp[n-1][4];}
}

题目限制了最多只能完成两笔交易(需要注意的是这里说的一笔交易是指买入和卖出两个动作,后续的题目也都是这个意思),dp[i][j]代表的是第i天的j状态下持有的金额为dp[i][j].

这个题目中dp[i][1]代表的是第i天是第一次买入(或者可以说是第一次持有股票),dp[i][2]代表的是第一次卖出股票(或第一次不持有股票的状态),dp[i][3]代表的是第二次持有股票的状态,dp[i][4]代表的是第二次不持有股票的状态.

2.AC代码:

class Solution {public int maxProfit(int k, int[] prices) {if(prices.length==0) return 0;int n=prices.length;int[][] dp=new int[n][k*2+1];for(int i=1;i<k*2;i+=2){dp[0][i]=-prices[0];}for(int i=1;i<n;i++){for(int j=0;j<k*2-1;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]);}}return dp[n-1][k*2];}
}

这个题和上面那个题目很类似,上面那个题是这个题中的一个,也就是说k=2的情况,仍然是一样的,一次交易分为两个动作(买入,卖出)所以k次交易的状态为k*2个.在这里我们下标0代表没有动作,下表为奇数代表买入,偶数代表卖出. 

3.AC代码:

class Solution {public int maxProfit(int[] prices) {int n=prices.length;if(n==0) return 0;int[][] dp=new int[n][4];dp[0][0]=-prices[0];for(int i=1;i<n;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]);// 状态三当天买出不能和状态2（步持有股票）合并，因为卖出股票后面紧接着的状态就是冻结！// 当天卖出dp[i][2]=dp[i-1][0]+prices[i];// 冻结期dp[i][3]=dp[i-1][2];}return Math.max(dp[n - 1][3], Math.max(dp[n - 1][1], dp[n - 1][2]));}
}

根据题目要求,我们可以将交易分为四个状态(持有,不持有,当日卖出,冷冻期),在这里需要注意的是,因为卖出股票的后一天一定会进入冷冻期,所以,在这里我们将当日卖出的操作从不持有股票这一大类中单独划出,这样更方便理解.