309. Best Time to Buy and Sell Stock with Cooldown

可以画出一个状态机:(无,rest)代表刚卖完股票,不能操作

例如对于有股票状态来说:

(有股票):1.卖掉 -> (无股票,rest); 2.rest -> (有股票)

所以可以写出dp方程式:

这里无股票用s0表示,有股票用s1表示,刚卖完股票用s2表示

s0[i] = max(s0[i - 1], s2[i - 1])
s1[i] = max(s1[i - 1], s0[i - 1] - prices[i])
s2[i] = s1[i - 1] + prices[i]

const maxProfit = function (prices) {
  if (prices.length <= 1) {
    return 0;
  }
  let s0 = [0], s1 = [-prices[0]], s2 = [Number.MIN_SAFE_INTEGER];
  // 这里无股票用s0表示,有股票用s1表示,刚卖完股票用s2表示
  for (let i = 1; i < prices.length; i++) {
    s0[i] = Math.max(s0[i - 1], s2[i - 1]);
    s1[i] = Math.max(s1[i - 1], s0[i - 1] - prices[i]);
    s2[i] = s1[i - 1] + prices[i];
  }
  return Math.max(s0[prices.length - 1], s1[prices.length - 1], s2[prices.length - 1]);
};

这种是比较好理解的方法

理解题意之后其实可以直接写出dp方程式:

对于每一天，有三种动作，buy, sell, cooldown, sell 和 cooldown 可以合并成一种状态，因为手里最终没有股票。最终需要的结果是 sell，即手里股票卖了获得最大利润。我们可以用两个数组来记录当前持股和未持股的状态，令sell[i] 表示第i天未持股时，获得的最大利润，buy[i]表示第i天持有股票时，获得的最大利润。

对于sell[i]，最大利润有两种可能，一是今天没动作跟昨天未持股状态一样，二是今天卖了股票，所以状态转移方程如下：

sell[i] = max{sell[i - 1], buy[i-1] + prices[i]}

对于buy[i]，最大利润有两种可能，一是今天没动作跟昨天持股状态一样，二是前天卖了股票，今天买了股票，因为 cooldown 只能隔天交易，所以今天买股票要追溯到前天的状态。状态转移方程如下：

buy[i] = max{buy[i-1], sell[i-2] - prices[i]}

然后巧妙地用几个变量来取代dp数组

const maxProfit = function (prices) {
  let sell = 0, prev_sell = 0, buy = Number.MIN_SAFE_INTEGER, prev_buy;
  // 这里无股票用s0表示,有股票用s1表示,刚卖完股票用s2表示
  for (let i = 0; i < prices.length; i++) {
    // buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i])
    // sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i])

    // 此时,prev_buy等于上上个循环中的prev_buy,prev_sell同理
    // buy和sell就是上个循环中的buy和sell
    prev_buy = buy;
    buy = Math.max(prev_buy, prev_sell - prices[i])
    prev_sell = sell;
    sell = Math.max(prev_sell, prev_buy + prices[i])
  }
  return sell;
};

const maxProfit = function (prices) {
  let sell = 0, prev_sell = 0, buy = Number.MIN_SAFE_INTEGER, prev_buy;
  for (let i = 0; i < prices.length; i++) {
    prev_buy = buy;
    buy = prev_buy > prev_sell - prices[i] ? prev_buy : prev_sell - prices[i];
    prev_sell = sell;
    sell = prev_sell > prev_buy + prices[i] ? prev_sell : prev_buy + prices[i];
  }
  return sell;
};