算法修炼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).