1、leetcode123 买卖股票的最佳时机Ⅲ
-
动规五步法
- dp[i] [j] : 在第i天,j状态下能获得的最大利润
- j = 0 : 第一次持有
- j = 1:第一次不持有
- j = 2:第二次持有
- j = 3:第二次不持有
- 递归公式
- dp[i] [0] = max( dp[i-1] [0] , -prices[i])
- 之前就处于第一次持有状态
- 当天第一次买入
- dp[i] [1] = max( dp[i-1] [1] , dp[i-1] [0] + prices[i] )
- 之前就处于第一次不持有的状态
- 当天第一次卖出
- dp[i] [2] = max(dp[i-1] [2],
dp[i-1] [0] - prices[i] + prices[i],dp[i-1] [1] - prices[i] )- 之前就处于第二次持有的状态
之前处于第一次持有的状态,当天进行第一次卖出以及第二次买入- 之前处于第一次不持有的状态,当天进行第二次买入
- dp[i] [3] = max( dp[i-1] [3] ,dp[i-1] [2] + prices[i]
, dp[i-1] [1], dp[i-1] [0]+prices[i])- 之前就处于第二次不持有的状态
- 之前处于第二次持有的状态,当天第二次卖出
之前处于第一次不持有的状态,当天进行第二次的买入、卖出之前处于第一次持有的状态,当天进行第一次卖出、第二次的买入、卖出
- dp[i] [0] = max( dp[i-1] [0] , -prices[i])
- 初始化
- dp[0] [0] = -prices[0]
- dp[0] [1] = 0
- dp[0] [2] = -prices[0]
- dp[0] [3] = 0
- 遍历顺序
- 从前向后遍历
- 举例
- dp[i] [j] : 在第i天,j状态下能获得的最大利润
-
代码
class Solution { public int maxProfit(int[] prices) { int[][] dp = new int[prices.length][4]; dp[0][0] = -prices[0]; dp[0][1] = 0; dp[0][2] = -prices[0]; dp[0][3] = 0; for(int i=1; i<prices.length; i++) { dp[i][0] = Math.max(dp[i-1][0] , -prices[i]); dp[i][1] = Math.max(dp[i-1][1] , dp[i-1][0] + 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]); } return dp[prices.length-1][3]; } }
2、leetcode188 买卖股票的最佳时机Ⅳ
-
dp[i] [j] : 在第i天,j状态下能获得的最大利润
- j为奇数表示持有状态;j为偶数表示不持有状态
-
代码
class Solution { public int maxProfit(int k, int[] prices) { if(prices.length == 0) return 0; int[][] dp = new int[prices.length][2*k+1]; for(int j=1; j<2*k; j+=2) { dp[0][j] = -prices[0]; } for(int i=1; i<prices.length; i++) { for(int j=1; j<2*k; j+=2) { dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1] - prices[i]); dp[i][j+1] = Math.max(dp[i-1][j+1], dp[i-1][j] + prices[i]); } } return dp[prices.length-1][2*k]; } }