状态机 DP：昨天赚了多少，还不够决定今天能做什么

最近审阅：2026-10 · 先读：回溯与 DP

这是一个常见的算法练习，不是投资建议：每天给一个价格，一次最多持有 1 份，卖出后第二天不能买入。问最后不持有时，最多能赚多少。

如果只记“到昨天为止最大收益”，你不知道那个收益来自刚卖出，还是已经休息了一天。两种情况的钱可能一样，今天允许的动作却不同。这就是需要额外状态的原因。

用明天能做什么，区分今天的状态

在每一天结束时，分成三类：

初始在任何交易之前：resting=0，另两个为负无穷，表示不可能。不能把 sold 也初始化成一个真实的成交记录。

resting ── buy ─────→ holding
holding ── sell ────→ sold
sold ──── cooldown → resting
resting ── stay ────→ resting
holding ── hold ────→ holding

箭头是跨一天的转移，不能在一天里沿多条箭头走。图的目的只是说明哪些状态相连；真正更新看下面的等式。

转移只读昨天，不能偷用今天的新值

第 $t$ 天价格为 $p_t$。用 $H,S,R$ 分别表示三种状态的最好收益：

$$ \begin{aligned} H_t&=\max(H_{t-1},R_{t-1}-p_t),\\ S_t&=H_{t-1}+p_t,\\ R_t&=\max(R_{t-1},S_{t-1}). \end{aligned} $$

持有可以来自继续持有，或昨天结束时处于 resting、今天买入；不能从昨天的 sold 买入。休息则可以来自继续休息，或昨天卖出后度过冷却日。

状态为什么足够？同一天、同一种状态下，未来可选动作相同，所以收益较小的历史不会比收益较大的更好。保留每种状态的最大值就够了。如果增加交易次数上限，这个论证要把“还剩几次”也放进状态。

手走一遍，比记三个变量有效

价格 [1,2,3,0,2]：

答案是 max(sold,resting)=3。可行路径是 1 买、2 卖、3 冷却、0 买、2 卖。第 4 天 holding=1 不代表“手里现金且没有资产”：它是扣除当前持仓成本后的净收益，不能直接当最后答案。

def cooldown_profit(prices):
    holding = float("-inf")
    sold = float("-inf")
    resting = 0
    for price in prices:
        holding, sold, resting = (
            max(holding, resting - price),
            holding + price,
            max(resting, sold),
        )
    return max(resting, sold)

Python 的多重赋值（元组解包）会先算完右边，再写左边，因此读的都是昨天。逐行覆盖三个变量，可能让后面的计算误读今天的新状态。输入约定是有限、非负价格；空列表返回 0。时间 $O(n)$，额外空间 $O(1)$；返回收益，不保留交易路径。

约束变了，状态或转移也要变

这是确定性序列上的 DP，不是强化学习（reinforcement learning, RL）：整条价格序列是题目输入，转移规则已知，没有学习策略的过程。它与 Bellman 思想有关，但别因为出现“状态”和“奖励（reward）”就叫它 RL。

检查时，专挑能破坏规则的例子

[1,2,3,0,2] 在没有冷却限制时答案是 4，有冷却时是 3，这能抓出遗漏约束的实现。全下降、只有一天、重复价格也要检查。

代码在 deeper_patterns.py。测试对短序列枚举所有合法买卖与等待动作，和这三个状态的结果比较；不是拿同一条递推式（recurrence relation）抄一遍当“独立答案”。公共练习可用 Stock with Cooldown，重点是学习如何补上影响未来选择的状态。