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

[!abstract] 问题 可以交易无限次，但卖出后有一天冷冻期（不能买入）。

示例

输入: prices = [1,2,3,0,2]
输出: 3
解释:
- 第1天买入(1)，第2天卖出(2)，利润=1
- 冷冻期(第3天)
- 第4天买入(0)，第5天卖出(2)，利润=2
- 总利润=3

解法

DP

function maxProfit(prices: number[]): number {
  const n = prices.length;
  if (n === 0) return 0;

  // dp[i][0] = 第 i 天不持有
  // dp[i][1] = 第 i 天持有
  // dp[i][2] = 第 i 天是冷冻期
  const dp = Array.from({ length: n }, () => Array(3).fill(0));
  dp[0][1] = -prices[0];

  for (let i = 1; i < n; i++) {
    dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2]);           // 继续不持有
    dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]); // 买入
    dp[i][2] = dp[i-1][1] + prices[i];                      // 卖出→冷冻
  }

  return Math.max(dp[n-1][0], dp[n-1][2]);
}

空间优化

function maxProfitOptimized(prices: number[]): number {
  let sold = 0, hold = -prices[0], rest = 0;

  for (let i = 1; i < prices.length; i++) {
    const prevSold = sold;
    sold = hold + prices[i];              // 卖出
    hold = Math.max(hold, rest - prices[i]); // 买入
    rest = Math.max(rest, prevSold);     // 保持冷冻或休息
  }

  return Math.max(sold, rest);
}

状态转移图

状态	转移
不持有	可买 or 继续不持有
持有	可卖
冷冻期	只能变回不持有

复杂度

时间	空间
O(n)	O(1)

---

参见: **股票问题** | **买卖股票最佳时机II** | **买卖股票含手续费**