day51

1、leetcode309 最佳买卖股票时机含冷冻期

1. 动规五部曲

   1. dp[i] [j] : 第i天状态j时，所能获得的最大金额
      • 持有股票 j=0
        • 之前就处于买入状态，之后无操作 dp[i] [0] = dp[i-1] [0]
        • 当天买入 (之前处于不持有股票状态，且要经历完一天冷冻期 ==》j=1，j=3)
      • 不持有股票
        • 前两天就卖出，刚经历完了一天的冷冻期 or 前一天就是卖出股票的状态，之后无操作（冷冻期过了很久了） j=1
        • 当天卖出 j=2（之前处于股票持有状态j=0）
      • 冷冻期
        • 当天为冷冻期 j=3（前一天处于卖出状态j=2）
   2. 递归公式
      1. dp[i] [0] = max( dp[i-1] [0], dp[i-1] [1]-prices[i], dp[i-1] [3]-prices[i] )
         1. 之前就处于买入状态，之后无操作
         2. 当天买入
            1. 前两天就卖出，经历完了一天的冷冻期后，当天买入【前一天为冷冻期】
            2. 前一天是保持卖出股票的状态
      2. dp[i] [1] = max( dp[i-1] [1]，dp[i-1] [3] )
         1. 前一天就是卖出股票的状态，之后无操作【j=1】
         2. 前两天就卖出，经历完了一天的冷冻期【前一天为冷冻期】【j=3】
      3. dp[i] [2] = dp[i-1] [0] + prices[i]
      4. dp[i] [3] = dp[i-1] [2]
   3. 初始化
      1. dp[0] [0] = -prices[0]
      2. dp[0] [1] = 0
      3. dp[0] [2] = 0
      4. dp[0] [3] = 0
   4. 遍历顺序
      • 从前向后遍历
   5. 举例

2. 代码

   class Solution {
       public int maxProfit(int[] prices) {
           int[][] dp = new int[prices.length][4];
           dp[0][0] = -prices[0];
   
           for(int i=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];
           }
   
           return Math.max(dp[prices.length-1][1], Math.max(dp[prices.length-1][2], dp[prices.length-1][3]));
   
       }
   }
   

2、leetcode714 买卖股票的最佳时机含手续费

1. 动规五部曲

   1. dp[i] [j] : 第i天状态j时，所能获得的最大金额
      • j=0：持有股票
        • 之前就处于持有状态，之后无操作
        • 当天买入（之前处于不持有状态）
      • j=1：不持有股票
        • 之前就处于不持有状态，之后无操作
        • 当天卖出，并扣除手续费（之前处于持有状态）
   2. 递归公式
      1. dp[i] [0] = max(dp[i-1] [0]，dp[i-1] [1] - prices[i])
      2. dp[i] [1] = max(dp[i-1] [1]，dp[i-1] [0] + prices[i] -fee)
   3. 初始化
      1. dp[0] [0] = -prices[0]
      2. dp[0] [1] = 0
   4. 遍历顺序
      • 从前往后遍历
   5. 举例

2. 代码

   class Solution {
       public int maxProfit(int[] prices, int fee) {
           int[][] dp = new int[prices.length][2];
           dp[0][0] = -prices[0];
   
           for(int i=1; i<prices.length; i++) {
               dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);
               dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i] - fee);
           }
   
           return dp[prices.length-1][1];
   
       }
   }