题目

给定股票价格数组，你可以多次交易，但卖出股票后第二天不能立刻再买入，问最大收益。

题目分析

这题不难想到“每天都做决策”，难的是状态不能只写成“买或不买”。

因为“刚卖出”这个状态会直接影响下一天是否允许买入，所以必须把状态拆细。

方法一：直觉解法

如果只用“持有 / 不持有”两个状态，冷冻期信息会丢失，转移很容易写错。

方法二：优化思路

更清晰的拆法是：

  • hold：当天结束时持有股票
  • sold：当天刚卖出股票
  • rest：当天结束时不持有且不在卖出当日

这样冷冻期就能自然表达出来。

Go 实现

 1func maxProfit(prices []int) int {
 2    if len(prices) == 0 {
 3        return 0
 4    }
 5
 6    hold := -prices[0]
 7    sold := 0
 8    rest := 0
 9
10    for i := 1; i < len(prices); i++ {
11        prevHold, prevSold, prevRest := hold, sold, rest
12        hold = max(prevHold, prevRest-prices[i])
13        sold = prevHold + prices[i]
14        rest = max(prevRest, prevSold)
15    }
16
17    return max(sold, rest)
18}
19
20func max(a, b int) int {
21    if a > b {
22        return a
23    }
24    return b
25}

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

易错点

  • sold 表示的是“当天刚卖出”，不是所有不持有状态
  • hold 的转移要从 rest 来，不能直接从 sold 来，因为冷冻期不允许次日买入

我的复盘

这题让我再次确认，动态规划里很多难点根本不在实现，而在状态设计。一旦状态拆得不够细，转移式就会看起来“差一点对”。