代码随想录算法训练营第51天|309. 买卖股票的最佳时机含冷冻期，714. 买卖股票的最佳时机含手续费，股票问题总结

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

这一题难在加入冷冻期后具体的状态难分析

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][4];

        // Initialization
        dp[0][0] = -prices[0]; // 买入股票
        dp[0][1] = 0; // 持续卖出股票的状态
        dp[0][2] = 0; // 具体卖出哪一张股票的状态
        dp[0][3] = 0; // 冷冻期

        for(int i = 1; i < len; i++){
            /** 状态一
                操作一：前一天就是持有股票状态（状态一），dp[i][0] = dp[i - 1][0]
                操作二：今天买入了，有两种情况
                    前一天是冷冻期（状态四），dp[i - 1][3] - prices[i]
                    前一天是保持卖出股票的状态（状态二），dp[i - 1][1] - prices[i]
            */
            dp[i][0] = Math.max(dp[i-1][0], Math.max(dp[i-1][1], dp[i-1][3]) - prices[i]);
            /** 状态二
                操作一：前一天就是状态二
                操作二：前一天是冷冻期（状态四）
             */
            dp[i][1] = Math.max(dp[i-1][1],dp[i][3]);
            /** 状态三
                即：dp[i][2] ，只有一个操作：

                昨天一定是持有股票状态（状态一），今天卖出

                即：dp[i][2] = dp[i - 1][0] + prices[i];
             */
            dp[i][2] = dp[i-1][0] + prices[i];
            /** 状态四
                即：dp[i][3]，只有一个操作：

                昨天卖出了股票（状态三）

                dp[i][3] = dp[i - 1][2];
             */
            dp[i][3] = dp[i-1][2];
        }

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

714. 买卖股票的最佳时机含手续费

这一题比上一题要简单一些

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int len = prices.length;
        // 0 : 持股（买入）
        // 1 : 不持股（售出）
        // dp 定义第i天持股/不持股 所得最多现金
        int[][] dp = new int[len][2];
        dp[0][0] = -prices[0];
        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1]);
        }
        return Math.max(dp[len - 1][0], dp[len - 1][1]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

总结

需要分析清楚股票的状态（持有，卖出等）然后根据不同的状态设置dp数组。同时也需要根据不同的状态推出递推公式

链接: 股票问题总结