动态规划之股票系列

123. 交易股票的最佳机遇 III
188. 交易股票的最佳机遇 IV
309. 交易股票的最佳机遇含冷冻期
1.AC代码:

1. class Solution {
2.     public int maxProfit(int[] prices) {
3.         int n=prices.length;
4.         int[][] dp=new int[n][5];
5.         dp[0][1]=-prices[0];
6.         dp[0][3]=-prices[0];
7.         for(int i=1;i<n;i++){
8.             // 第一次买入
9.             dp[i][1]=Math.max(dp[i-1][1],-prices[i]);
10.             // 第一次卖出
11.             dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);
12.             // 第二次买入
13.             dp[i][3]=Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);
14.             // 第二次卖出
15.             dp[i][4]=Math.max(dp[i-1][4],dp[i-1][3]+prices[i]);
16.         }
17.         return dp[n-1][4];
18.     }
19. }

复制代码

题目限制了最多只能完成两笔交易业务(必要注意的是这里说的一笔交易业务是指买入和卖出两个动作,后续的题目也都是这个意思),dp[j]代表的是第i天的j状态下持有的金额为dp[j].
这个题目中dp[1]代表的是第i天是第一次买入(或者可以说是第一次持有股票),dp[2]代表的是第一次卖出股票(或第一次不持有股票的状态),dp[3]代表的是第二次持有股票的状态,dp[4]代表的是第二次不持有股票的状态.
2.AC代码:

1. class Solution {
2.     public int maxProfit(int k, int[] prices) {
3.         if(prices.length==0) return 0;
4.         int n=prices.length;
5.         int[][] dp=new int[n][k*2+1];
6.         for(int i=1;i<k*2;i+=2){
7.             dp[0][i]=-prices[0];
8.         }
9.         for(int i=1;i<n;i++){
10.             for(int j=0;j<k*2-1;j+=2){
11.                 // 奇数买入
12.                 dp[i][j+1]=Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i]);
13.                 // 偶数卖出
14.                 dp[i][j+2]=Math.max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);
15.             }
16.         }
17.         return dp[n-1][k*2];
18.     }
19. }

复制代码

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

1. class Solution {
2.     public int maxProfit(int[] prices) {
3.         int n=prices.length;
4.         if(n==0) return 0;
5.         int[][] dp=new int[n][4];
6.         dp[0][0]=-prices[0];
7.         for(int i=1;i<n;i++){
8.             // 持有股票
9.             dp[i][0]=Math.max(dp[i-1][0],Math.max(dp[i-1][1]-prices[i],dp[i-1][3]-prices[i]));
10.             // 不持有股票
11.             dp[i][1]=Math.max(dp[i-1][1],dp[i-1][3]);
12.             // 状态三当天买出不能和状态2（步持有股票）合并，因为卖出股票后面紧接着的状态就是冻结！
13.             // 当天卖出
14.             dp[i][2]=dp[i-1][0]+prices[i];
15.             // 冻结期
16.             dp[i][3]=dp[i-1][2];
17.         }
18.          return Math.max(dp[n - 1][3], Math.max(dp[n - 1][1], dp[n - 1][2]));
19.     }
20. }

复制代码

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


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。