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

题目描述

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

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

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例

示例 1:

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

示例 2:

• 输入: prices = [1]
• 输出: 0

---

解题思路

第一步：理解问题本质

本题是经典的“买卖股票”系列变体。核心约束在于冷冻期：卖出股票后的第一天不能买入。这意味着如果第 $i$ 天卖出，第 $i+1$ 天必须休息，最早只能在第 $i+2$ 天买入。我们需要通过动态规划（DP）或状态机来记录每天结束时的最大利润。

第二步：暴力解法

暴力法通过递归尝试每一天的所有可能操作（买入、卖出、持有、休息）。

• 思路：dfs(day, hold, cooldown) 表示从某天开始的最大利润。
• 缺点：每天有多个选择，时间复杂度为 $O(4^n)$，对于较大的数组会产生大量重复计算导致超时。

第三步：优化解法（记忆化搜索）

通过引入缓存（Cache）来消除重复计算。

• 状态定义：dfs(i, hold) 表示从第 $i$ 天开始，当前是否持有股票所能获得的最大利润。
• 转移逻辑：
  • 如果持有：可以选择继续持有或卖出（卖出后下一天冷冻，跳到 $i+2$）。
  • 如果未持有：可以选择继续休息或买入（买入后进入持有状态）。
• 复杂度：时间复杂度优化至 $O(n)$，但仍有 $O(n)$ 的空间开销。

第四步：最优解法（状态压缩 DP）

将递归转为迭代，并观察到每天的状态只与前两天有关，从而将空间优化到 $O(1)$。

我们定义三个变量来表示每天结束时的状态：

1. f0: 第 $i$ 天结束时，不持有股票的最大利润。
2. f1: 第 $i$ 天结束时，持有股票的最大利润。
3. pre0: 第 $i-1$ 天结束时，不持有股票的最大利润（即前天的不持有状态，用于处理冷冻期）。

状态转移方程：

• 新的 f0 = $\max(\text{旧 f0}, \text{旧 f1} + \text{当前价格})$ （保持不持有或今天卖出）
• 新的 f1 = $\max(\text{旧 f1}, \text{pre0} - \text{当前价格})$ （保持持有或今天买入，买入必须跨过冷冻期，故使用 pre0）

---

完整代码实现

from typing import List
from math import inf

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # f0: 当前不持有股票的最大利润
        # f1: 当前持有股票的最大利润
        # pre0: 前一天不持有股票的最大利润（用于判断冷冻期）
        pre0, f0, f1 = 0, 0, -inf
        
        for p in prices:
            # 记录当前 f0，它将成为下一轮循环的 pre0
            new_f0 = max(f0, f1 + p)
            new_f1 = max(f1, pre0 - p)
            
            # 更新状态
            pre0 = f0
            f0 = new_f0
            f1 = new_f1
            
        return f0

---

示例推演

以 prices = [1, 2, 3, 0, 2] 为例：

天数	价格	初始 pre0	初始 f0	初始 f1	操作	更新后 f0	更新后 f1	下轮 pre0
初始	-	0	0	-inf	-	0	-inf	0
Day 0	1	0	0	-inf	买入	0	-1	0
Day 1	2	0	0	-1	卖出	1	-1	0
Day 2	3	0	1	-1	持有	2	-1	1
Day 3	0	1	2	-1	买入	2	1	2
Day 4	2	2	2	1	卖出	3	1	2

最终结果：f0 = 3。

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
暴力	$O(4^n)$	$O(n)$	递归深度带来的空间开销，超时
记忆化搜索	$O(n)$	$O(n)$	使用哈希表或数组存储中间结果
状态压缩 DP	$O(n)$	$O(1)$	仅使用常数级变量，最优空间

---

易错点总结

1. 初始状态设置：f1（持有状态）应初始化为 -inf，因为在买入之前不可能持有股票。
2. 冷冻期理解：买入股票时，利润必须从“前天不持有”的状态转移而来，而不是“昨天不持有”。
3. 状态更新顺序：在迭代更新时，要注意变量覆盖问题，或者使用元组赋值 pre0, f0, f1 = f0, max(f0, f1 + p), max(f1, pre0 - p)。

---

扩展思考

本题是“买卖股票”问题的进阶版。如果冷冻期变为 $k$ 天，我们需要维护一个长度为 $k+1$ 的队列或数组来记录不持有状态的更早历史。状态机 DP 的通用性在于只要理清了状态之间的转化逻辑，任何复杂的约束条件都可以通过增加状态维度来解决。

---

相关题目

• 121. 买卖股票的最佳时机
• 122. 买卖股票的最佳时机 II
• 714. 买卖股票的最佳时机含手续费