冷冻期股票问题的核心分析

LeetCode上的冷冻期股票问题（309. Best Time to Buy and Sell Stock with Cooldown）要求计算在卖出股票后需要等待一天冷冻期的限制下，能获得的最大利润。关键在于定义清楚每个状态及其转移关系。

状态定义与转移方程

设定三种状态：

• hold[i]：第i天结束时持有股票的最大利润
• not_hold[i]：第i天结束时不持有股票且处于冷冻期的最大利润
• free[i]：第i天结束时不持有股票且不处于冷冻期的最大利润

状态转移方程：

• hold[i] = max(hold[i-1], free[i-1] - prices[i])
  保持持有状态或从非冷冻期买入

• not_hold[i] = hold[i-1] + prices[i]
  只有卖出操作会进入冷冻期

• free[i] = max(free[i-1], not_hold[i-1])
  保持非冷冻状态或从冷冻期解冻

边界条件处理

初始状态设置：

• hold[0] = -prices[0]
  第一天只能买入

• not_hold[0] = -infinity
  第一天不可能处于冷冻期

• free[0] = 0
  第一天未操作

空间优化技巧

由于状态只依赖前一天的记录，可将空间复杂度从O(n)优化到O(1)：

prev_hold, prev_not_hold, prev_free = -prices[0], -float('inf'), 0
for price in prices[1:]:
    curr_hold = max(prev_hold, prev_free - price)
    curr_not_hold = prev_hold + price
    curr_free = max(prev_free, prev_not_hold)
    prev_hold, prev_not_hold, prev_free = curr_hold, curr_not_hold, curr_free
return max(prev_not_hold, prev_free)

常见错误排查

1. 混淆冷冻期定义
   冷冻期仅限制卖出后的第二天不能买入，不影响连续持有

2. 状态转移遗漏
   容易忽略free[i]可以从not_hold[i-1]转移的情况

3. 初始化错误
   not_hold[0]应设为无效值而非0，因为第一天不可能因卖出进入冷冻期

复杂度分析

时间复杂度：O(n)
只需遍历价格数组一次

空间复杂度：O(1)
通过变量复用实现常数空间

扩展思考

该问题可延伸至含交易手续费的情况，只需在卖出操作时扣除费用：

curr_not_hold = prev_hold + price - fee

状态机的设计方法同样适用于其他限制条件的股票问题，如交易次数限制等。