【动态规划】309. 买卖股票的最佳时机含冷冻期、 714. 买卖股票的最佳时机含手续费

提示：努力生活，开心、快乐的一天

---

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

题目链接：309. 买卖股票的最佳时机含冷冻期

💡解题思路

动规五部曲：

• 确定dp数组以及下标的含义：**dp[i][j]，第i天状态为j，所剩的最多现金为dp[i][j]。**主要分为四种状态：
  0：持有股票状态（今天买入股票，或者是之前就买入了股票然后没有操作，一直持有）
  1：不持有股票状态1:保持卖出股票的状态（两天前就卖出了股票，度过一天冷冻期。或者是前一天就是卖出股票状态，一直没操作）
  2：不持有股票状态2:今天卖出股票
  3：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！
• 确定递推公式：
  达到买入股票状态（状态一）即：dp[i][0]，有两个具体操作
  1、 操作一：前一天就是持有股票状态（状态一），dp[i][0] = dp[i - 1][0]
  2、 操作二：今天买入了，有两种情况：
  前一天是冷冻期（状态四），dp[i - 1][3] - prices[i]；
  前一天是保持卖出股票的状态（状态二），dp[i - 1][1] - prices[i]
  dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i])
  达到保持卖出股票状态（状态二）即：dp[i][1]，有两个具体操作:
  1、操作一：前一天就是状态二
  2、操作二：前一天是冷冻期（状态四）
  dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3])
  达到今天就卖出股票状态（状态三），即：dp[i][2] ，只有一个操作：
  昨天一定是持有股票状态（状态一），今天卖出
  dp[i][2] = dp[i - 1][0] + prices[i];
  达到冷冻期状态（状态四），即：dp[i][3]，只有一个操作：
  昨天卖出了股票（状态三）
  dp[i][3] = dp[i - 1][2];
• dp数组如何初始化：
  第0天状态一，dp[0][0] = -prices[0]，一定是当天买入股票
  第0天状态二 ，dp[0][1] = 0;
  第0天状态三，dp[0][2] = 0；
  第0天状态四，dp[0][3] = 0;
• 确定遍历顺序：从递推公式可以看出dp[i]都是由dp[i - 1]推导出来的，那么一定是从前向后遍历。
• 举例推导dp数组：按照递推公式推导一下做推导，如果发现结果不对，就把dp数组打印出来
  最后结果是取 状态二，状态三，和状态四的最大值，状态四是冷冻期，最后一天如果是冷冻期也可能是最大值。

🤔遇到的问题

1. dp数组初始化的时候，出错了 ，应该初始化为四维数组

💻代码实现

动态规划

var maxProfit = function(prices) {
  // 0：持有股票状态（今天买入股票，或者是之前就买入了股票然后没有操作，一直持有）
  // 1：不持有股票状态1:保持卖出股票的状态（两天前就卖出了股票，度过一天冷冻期。或者是前一天就是卖出股票状态，一直没操作）
  // 2：不持有股票状态2:今天卖出股票
  // 3：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！
let len = prices.length;
if(len < 2) return 0;
else if(len<3) return Math.max(0,prices[1]-prices[0])
let dp = Array.from(Array(len), () => Array(4).fill(0));
dp[0][0] = -prices[0]
for(let i=1; i<len; i++){
  dp[i][0] = Math.max(dp[i-1][0],dp[i-1][3]-prices[i],dp[i-1][1]-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[len-1][1],dp[len-1][2],dp[len-1][3])
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

🎯题目总结

1. 四个状态梳理清楚了就比较简单了
   0：持有股票状态（今天买入股票，或者是之前就买入了股票然后没有操作，一直持有）
   1：不持有股票状态1:保持卖出股票的状态（两天前就卖出了股票，度过一天冷冻期。或者是前一天就是卖出股票状态，一直没操作）
   2：不持有股票状态2:今天卖出股票
   3：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！

---

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

题目链接：714. 买卖股票的最佳时机含手续费

💡解题思路

1. 相对于动态规划：122.买卖股票的最佳时机II (opens new window)，本题只需要在计算卖出操作的时候减去手续费就可以了，代码几乎是一样的。
   唯一差别在于递推公式部分，所以主要讲解一下递推公式部分。
2. dp[i][0] 表示第i天持有股票所得 最多现金。 dp[i][1] 表示第i天不持有股票所得最多现金
   如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来
   1、 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
   2、今第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1][1] - prices[i]
   dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i])
   如果第i天不持有股票即dp[i][1]的情况， 依然可以由两个状态推出来
   1、第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
   2、第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金，注意这里需要有手续费了即：dp[i - 1][0] + prices[i] - fee
   dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee)

🤔遇到的问题

1. 只有两个状态，滤清两个状态即可

💻代码实现

暴力解法

var maxProfit = function(prices, fee) {
  //dp[i][0] 表示第i天持有股票所得最多现金
  // dp[i][1] 表示第i天不持有股票所得最多现金
  let len = prices.length;
  let dp = new Array(len).fill([0,0])
  dp[0][0] = -prices[0]
  for(let 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][1],dp[i-1][0]+prices[i]-fee)
  }
  return Math.max(dp[len-1][0],dp[len-1][1])
};
1
2
3
4
5
6
7
8
9
10
11
12

🎯题目总结

只有卖出股票才会有手续费

🎈今日心得