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

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

309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）

1.思路

初始化dp[i][j]数组，表示第i天的最大利润为dp[i][j].
精确的定义状态是个难点，可以定义四种状态：持有股票（当天买入、前一天持有、前一天为保持卖出的状态）、卖出状态（前一天为冷冻期、前一天为卖出状态）、卖出股票（前一天持有股票当天卖出+prices[i]）、冷冻期（前一天卖出的状态）

2.代码实现

 1class Solution {2    public int maxProfit(int[] prices) {345        int len = prices.length;67        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

3.复杂度分析

时间复杂度：O(n).
空间复杂度：O(n).

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

714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）

1.思路

初始化dp[][][]数组，确定两种状态：持有股票和不持有股票，进行状态转移推演即可。

2.代码实现

 1class Solution {2    public int maxProfit(int[] prices, int fee) {3        int len = prices.length;45        // dp[i][j]67        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

3.复杂度分析

时间复杂度：O(n).
空间复杂度：O(n).