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

题目链接（中等）

题目描述

给定一个整数数组 prices，其中第 prices[i] 表示第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）：

• 卖出股票后，你无法在第二天买入股票（即冷冻期为 1 天）；
• 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

数据范围：

• 1 <= prices.length <= 5000
• 0 <= prices[i] <= 1000

示例

示例 1：

输入： prices = [1,2,3,0,2]
输出： 3
解释： 对应的交易状态为 [买入, 卖出, 冷冻期, 买入, 卖出]。

示例 2：

输入： prices = [1]
输出： 0

核心思路

股票类问题的通用思路：把「买入」和「卖出」看作收益的加减。

• 买入：收益 -prices[i]（花出去的钱）；
• 卖出：收益 +prices[i]（收回来的钱）。

由于有冷冻期限制，需要额外追踪「今天是否处于冷冻期」。

关键：用状态机描述每天结束后的状态，然后写出状态转移方程。

本题有三种状态：

1. 持有股票（f0）：手里还有股票；
2. 不持有股票、处于冷冻期（f1）：今天刚卖出，明天不能买；
3. 不持有股票、不在冷冻期（f2）：可以自由买入。

对每一天，从上一天的状态出发，枚举可以做的操作，取收益最大值。

---

方法一：状态机 DP（二维数组）

思路及解法

定义 f[i][0]、f[i][1]、f[i][2] 分别表示第 i 天结束后处于三种状态时的累计最大收益：

• f[i][0]：持有股票；
• f[i][1]：不持有股票，且处于冷冻期；
• f[i][2]：不持有股票，且不处于冷冻期。

状态转移：

f[i][0]（持有股票）：

• 情况一：第 i-1 天就持有，第 i 天不动 → f[i-1][0]；
• 情况二：第 i 天买入，则第 i-1 天必须「不持有且不在冷冻期」 → f[i-1][2] - prices[i]。

$$f[i][0] = \max(f[i-1][0],\ f[i-1][2] - prices[i])$$

f[i][1]（不持有、冷冻期）：

• 唯一来源：第 i 天卖出了股票，则第 i-1 天必须持有 → f[i-1][0] + prices[i]。

$$f[i][1] = f[i-1][0] + prices[i]$$

f[i][2]（不持有、非冷冻期）：

• 情况一：第 i-1 天处于冷冻期，第 i 天什么都没做 → f[i-1][1]；
• 情况二：第 i-1 天也不持有且不在冷冻期 → f[i-1][2]。

$$f[i][2] = \max(f[i-1][1],\ f[i-1][2])$$

边界条件（第 0 天）：

• f[0][0] = -prices[0]：第 0 天买入，负收益；
• f[0][1] = 0：第 0 天不存在冷冻期，但值仍为 0，便于后续转移；
• f[0][2] = 0：第 0 天不买不卖，收益 0。

答案：max(f[n-1][1], f[n-1][2])。

最后一天如果还持有股票（f[n-1][0]），说明没卖出去，收益不是最优，不参与比较。

代码

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        if not prices:
            return 0

        n = len(prices)
        # f[i][0]: 持有股票
        # f[i][1]: 不持有，处于冷冻期
        # f[i][2]: 不持有，不在冷冻期
        f = [[-prices[0], 0, 0]] + [[0] * 3 for _ in range(n - 1)]

        for i in range(1, n):
            f[i][0] = max(f[i - 1][0], f[i - 1][2] - prices[i])
            f[i][1] = f[i - 1][0] + prices[i]
            f[i][2] = max(f[i - 1][1], f[i - 1][2])

        return max(f[n - 1][1], f[n - 1][2])

复杂度分析

• 时间复杂度：$O(n)$，遍历一次数组。
• 空间复杂度：$O(n)$，f 数组共 3n 个状态。

---

方法二：滚动变量（$O(1)$ 空间）

思路及解法

f[i][*] 只依赖 f[i-1][*]，所以可以用三个变量滚动更新。

关键：计算新状态时，必须先保存上一轮的值，否则会互相污染。

f0, f1, f2 = -prices[0], 0, 0

for i in range(1, n):
    newf0 = max(f0, f2 - prices[i])   # 持有股票
    newf1 = f0 + prices[i]            # 卖出，进入冷冻期
    newf2 = max(f1, f2)               # 不持有，不在冷冻期
    f0, f1, f2 = newf0, newf1, newf2

为什么 newf1 用的是旧 f0？

因为 newf1 表示「今天卖出」，前提是昨天持有股票。这里的 f0 是上一轮（昨天）持有股票的状态，不是今天更新后的。Python 中 newf0, newf1, newf2 先全部算出来，再一次性赋值给 f0, f1, f2，所以不会污染。

代码

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        if not prices:
            return 0

        f0 = -prices[0]     # 持有股票
        f1 = 0              # 不持有，冷冻期
        f2 = 0              # 不持有，非冷冻期

        for i in range(1, len(prices)):
            newf0 = max(f0, f2 - prices[i])
            newf1 = f0 + prices[i]
            newf2 = max(f1, f2)
            f0, f1, f2 = newf0, newf1, newf2

        return max(f1, f2)

复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$，只使用三个变量。

---

两种方法对比

方法	时间	空间	特点
二维 DP	$O(n)$	$O(n)$	状态清晰，便于理解
滚动变量	$O(n)$	$O(1)$	空间最优，面试推荐

推荐：

• 面试开场：先用二维 DP 讲清三种状态的转移关系；
• 优化：再说明「只依赖上一轮」，滚动到 $O(1)$ 空间。

---

关键细节

1. 为什么需要三种状态

冷冻期导致「不持有股票」被拆成两种：处于冷冻期和不处于冷冻期。这两者的可买入性不同：

• 冷冻期：明天不能买；
• 非冷冻期：明天可以买。

所以状态机必须区分。

2. 冷冻期的定义

题目的冷冻期是「卖出股票后的第二天不能买入」。

在状态机里，f[i][1] 表示「第 i 天结束后处于冷冻期」，意味着第 i+1 天不能买入。第 i+2 天就可以买了。

3. f[0][1] = 0 的合理性

第 0 天不存在冷冻期，但为了代码转移方便，把它设为 0。这样 f[1][2] = max(f[0][1], f[0][2]) = 0，逻辑上正确。

4. 为什么答案是 max(f1, f2) 而不是 max(f0, f1, f2)

最后一天如果还持有股票，说明没卖出，这部分股票的价值并没有变现。而题目要的是收益（已经实现的利润），所以不能把 f0 计入答案。

5. 与 LC 122（买卖股票的最佳时机 II）的对比

	LC 122	LC 309
冷冻期	无	1 天
状态	持有 / 不持有	持有 / 冷冻 / 非冷冻
转移	f0 = max(f0, f1 - p)	f0 = max(f0, f2 - p)

LC 309 比 LC 122 多一个「冷冻期」状态，f0 的转移来源从 f1（不持有）改成 f2（不持有且不在冷冻期）。

---

总结

• 状态机三状态：
  • f0：持有股票；
  • f1：不持有，处于冷冻期；
  • f2：不持有，不在冷冻期；
• 转移方程：
  • f0 = max(f0, f2 - prices[i])；
  • f1 = f0(旧) + prices[i]；
  • f2 = max(f1(旧), f2(旧))；
• 边界：f0 = -prices[0]，f1 = f2 = 0；
• 答案：max(f1, f2)；
• 空间优化：滚动变量，降到 $O(1)$；
• 通用套路：股票类问题用状态机 DP，每种状态对应「某天结束后的持仓情况」，转移时枚举可以做的操作。

相关题目

• LC 121. 买卖股票的最佳时机（只能交易一次）
• LC 122. 买卖股票的最佳时机 II（可以交易多次）
• LC 123. 买卖股票的最佳时机 III（最多两次交易）
• LC 188. 买卖股票的最佳时机 IV（最多 k 次交易）
• LC 714. 买卖股票的最佳时机含手续费（和本题类似，只是把手续费换成手续费）