算法修炼Day51|● 309.最佳买卖股票时机含冷冻期 ● 714.买卖股票的最佳时机含手续费

 1class Solution {
 2    public int maxProfit(int[] prices) {
 3
 4
 5        int len = prices.length;
 6
 7        int[][] dp = new int[len][4];
 8        // 四种状态
 9        // dp[i][0] 持有股票；dp[i][1] 保持卖出股票；dp[i][2]卖出股票；dp[i][3]冷冻期
10
11
12        // 初始化dp数组
13        dp[0][0] = -prices[0];
14        dp[0][1] = 0;
15        dp[0][2] = 0;
16        dp[0][3] = 0;
17
18        for (int i = 1; i < len; i++) {
19            // 持有股票：①前一天持有 ②当天买入 ③冷冻期下一天买入
20            dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));
21            // 保持卖出股票：①冷冻期②前一天就是保持卖出状态
22            dp[i][1] = Math.max(dp[i - 1][3], dp[i - 1][1]);
23            // 卖出股票操作
24            dp[i][2] = dp[i - 1][0] + prices[i];
25            // 冷冻期
26            dp[i][3] = dp[i - 1][2];
27        }
28
29        return Math.max(dp[len - 1][1], Math.max(dp[len - 1][2], dp[len - 1][3]));
30    }
31}
32

 1class Solution {
 2    public int maxProfit(int[] prices, int fee) {
 3        int len = prices.length;
 4
 5        // dp[i][j]
 6
 7        int[][] dp = new int[len][2];
 8        dp[0][0] = -prices[0];
 9        // dp[0][1] = 0; 
10        for (int i = 1; i < len; i++) {
11            // 持有状态：①当天买入；②前一天持有
12            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
13            // 不持有状态：①前一天就是卖出状态；②当天卖出
14            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
15        }
16
17        return dp[len - 1][1];
18    }
19}
20