【算法】动态规划第六篇：状态机 DP——股票家族全集与三例副作用死刑
【算法】动态规划第六篇：状态机 DP——股票家族全集与三例副作用死刑 摘要 DP 系列第六篇，第 5 级状态机 DP 全记录。股票家族五题一网打尽：121（暴力 O(n²) 起步 → hold/cash 双状态机 + 前缀最小版双轨）、122（自创"落袋贪心"碰巧正确但无法论证，死刑于扩展性；状态机改一行）、188（k 次交易 = 状态加一层楼；j=0 地基层漏算导致"股票白送"）、309（冷冻期
文章信息
- 原文链接：https://jiayq.blog.csdn.net/article/details/164458000
- 发布时间：2026-09-20 20:11:37
- 标签：#Golang, #算法, ##状态机, ##算法讲解
【算法】动态规划第六篇：状态机 DP——股票家族全集与三例副作用死刑
摘要
DP 系列第六篇，第 5 级状态机 DP 全记录。股票家族五题一网打尽：121 （暴力 O(n²) 起步 → hold/cash 双状态机 + 前缀最小版双轨）、122 （自创”落袋贪心”碰巧正确但无法论证，死刑于扩展性；状态机改一行）、188 （k 次交易 = 状态加一层楼；j=0 地基层漏算导致”股票白送”）、309 （冷冻期 = cash 分裂出一个状态；”贪心跳天”和 i-2 过严两连坑）、714 （手续费 = 一条转移改一个常数）。本篇的核心心法只有一句：状态机的禁令永远写在转移边上，不写在状态定义里 ；外加三个反复现身的幽灵：“不动”分支 （max 的左半边，五次现身）、传钱通道 （买入本金 = 口袋全部现金，0 元买入是照妖镜）、以及三例”用副作用模拟状态”的死刑记录 （落袋贪生、跳天生、sale 标记生）。还有一张拉锯了七轮的手推表——它一个人贡献了本篇一半的教训。
前置阅读：动态规划第五篇：区间DP——从看什么都像背包到最后戳谁。配套代码仓库（按题号分目录）：https://github.com/a18792721831/studyleetCode
1. LC121：双状态机的诞生
只许交易一次，求最大利润。
[7,1,5,3,6,4]→ 5。
起点是一张暴力表（所有买卖对的利润矩阵）和 O(n²) 双重循环——自己诊断出”超时 + 没用 dp”。
1.1 第一层：前缀最小（从自己的表里挖）
盯暴力表：固定卖出日 j，最优买入日 = j 之前价格最低的那天 ——内层循环变成一个边扫边维护的变量，O(n²) → O(n)。
这一层挖出了两个坑：初版写成”找全局最低点再往后扫”——[2,10,1,3] 输出 2（正确 8，2 买 10 卖被太晚的全局最低点葬送）。全局最小是绝对概念，前缀最小是相对概念 ——“对每个卖出日，最优买点是它之前的最低”，这个”之前”随 j 移动。第二坑是笔误 max(prices[i]-buy) 单参数——max 的第一个参数就是”不动”分支，两个参数一个都不能少 。
1.2 第二层：状态机（为什么值得多学一个框架）
一维 dp[i] 装不下这题——同一个”第 i 天”有两种截然不同的处境：手里有股票 / 没有股票 。状态机登场：
1
2
3
4
5
hold[i] = 第 i 天结束仍持有股票的最大现金
cash[i] = 第 i 天结束空仓的最大现金
hold[i] = max(hold[i-1], -prices[i]) ← 继续拿 / 今天买
cash[i] = max(cash[i-1], hold[i-1]+prices[i]) ← 继续空 / 今天卖
手推 [7,1,5,3,6,4] 时翻的坑（本篇第一个重要教训）：cash 行的 day3、day5 写错——只算了”今天卖出”，max 的左半边（昨天状态的延续，今天什么都不做）没执行 。cash[3] = max(4, 2) = 4 的含义是”第 3 天最优策略是第 1 天买第 2 天卖赚 4，第 3 天什么都不做 “——不动是一个合法且常常最优的决策 ，状态机的”不动”转移就是给它建模的。
两个版本的对照实验回答了”为什么要学状态机”：
| 前缀最小/贪心版 | 状态机版 | |
|---|---|---|
| 121 | 语义坑（全局 vs 前缀）+ 笔误，三轮修复 | 一次过 |
| 122 | 推倒重来 | 改一条转移 |
贪心/前缀技巧是一次性聪明，状态机是可扩展框架。
2. LC122：第一例副作用死刑——落袋贪生
无限次交易。
[7,1,5,3,6,4]→ 7。
第一版自创了”落袋贪心 “：浮盈为正就落袋（ans += cash）、当天原价重新建仓（cash=0; hold=-prices[i]）。它在 122 上碰巧正确 （等价于吃掉所有正差分），但作者自己的不安（“我感觉是不对的……隐含一个条件”）才是真相：无法论证自己为什么对的解，和碰巧对没有区别 。
死刑判决在扩展性：188（数不了交易次数）、309（”今天落袋今天买回”违反冷冻规则）——用运行时副作用模拟状态，一遇变体就死 。
2.1 正解：改一行
1
2
hold[i] = max(hold[i-1], cash[i-1] - prices[i]) ← 唯一改动：买入本金从昨天的 cash 带过来
为什么必须 cash[i-1]：hold[i] 先算，此刻 cash[i] 还没算——读到的是零值垃圾。
2.2 传钱通道：day3 的 hold 第一次出现正值
1
2
3
4
7 1 5 3 6 4
hold -7 -1 -1 1 1 3
cash 0 0 4 4 7 7
hold[3] = 1：day2 卖出攒了 4，day3 花 3 买回——持仓里除了股票还揣着 1 块利润 。无限次交易的本质：没有落袋清零，利润随状态一路流动 。落袋贪心用”清零+重买”绕出来的效果，状态机用”本金流动”直接表达——买入分支的本金永远是”当前手里的全部现金”，不是股价 。这个”传钱通道”在 122/312/309/188 出现四次，是整个家族的血管。
3. LC188：状态加一维——一层一次交易
最多 k 笔交易。
[3,2,6,5,0,3], k=2→ 7。
思考题”k 从哪里进状态”的答案：k 不是下标、不是计数器，是状态本身 ——hold[j][i] / cash[j][i]，hold 和 cash 各自分裂成 k 份。”做了几笔”和”持不持仓”一样，是”今天结束时我是谁”的一部分。自己悟出的表述最准：一层一次交易 。
两个工程坑：
- 不可能状态哨兵 ：
hold[j≥1][0] = -MaxInt（第 0 天完不成两步交易）——max 世界的”小而无害”，填 0 等于凭空有本金 - 答案取 max over j ：”最多 k 笔”允许在任意低层躺平，最优可能在任何一层
3.1 地基级 bug：j=0 层整层没算
第一版的循环 for j := 1 把 j=0 层跳过了——hold[0][i≥1] 全是 make 零值 0，而 cash[1] 的卖出转移读它：
1
2
3
cash[1][i] = max(..., hold[0][i-1] + prices[i]) ← 读到零值 0
[7,6,4,3,1]（全程下跌）输出 4：cash[1][2] = 0 + 4 = 4——股票白送，没付一分钱买入
零值能白送的格子，前提是它的语义恰好等于 0 （cash[0] 恒 0 ✓）；hold[0] 的语义是负数（负的前缀最小），零值就是毒。j=0 层不是装饰，是活的地基——必须单独跑一轮转移。
3.2 一张拉锯七轮的手推表
188 的手推表（[3,2,6,5,0,3], k=2 三层）从第一版到最终版走了七轮，每一轮都是一类错误的标本：
- 残骸复制 ：j=0 层
cash行的一个 4（来自第一版把 j=1 层的值填错位置），六轮打补丁都没删——在旧表残骸上打补丁，残骸不删，错误永生 。最后重画满格对齐的新表才清零 - 串层 ：j=1 的值漏进 j=0、j=2 的终值 7 漏进 j=1——每层只写”有值的尾巴”不对齐是温床
- 改对迁就错 ：发现
hold=0, sold=3自相矛盾后，把对的sold改成 2 去匹配错的hold——矛盾是 bug 的报警器，拆报警器不灭火 。自洽不是目的，正确才是 - 带利润买入 反复：
hold[j][4] = -prices[4] = -0 = 0（121 旧转移）vscash[j][3]-prices[4] = 4-0 = 4——与 309 同款，详见下节 - 只推答案行 ：sold/cash（答案来源）逐格认真，hold/free（依赖行）随手凑——每一行都是下一行的依赖，答案行的对是无根之木
最终这张表的修复方式也值得记录：跑自己的代码（七用例全绿的 188）打印三层表，对着打印结果誊写，誊写时每格标注 max 的哪边赢 ——互证规定动作这题从来没做过，补上它，七轮拉锯一朝清账。
4. LC309：加一个状态——冷冻期
卖出后冷冻一天。
[1,2,3,0,2]→ 3。
手推时的自问自答一针见血：“难点：冷静期怎么处理？直接下标跳 1？ ”——问题极准，答案就是本节全部：不跳下标，加状态 。
4.1 第二例副作用死刑：跳天生
第一版用 sale 布尔标记 + continue 跳天模拟冷冻。死因两个：
- 贪心判定丢路径 ：
if 卖出比不卖好 { sale = true }——[1,3,5]在 i=1（价格 3）就卖（2 > 0），”拿到 5”的路径当场死亡。输出 2，正确 4。“今天卖还是继续拿”是需要 max 权衡的决策，贪心一口咬定就丢分支 - 跳天把世界饿死 ：冷冻期不是”跳过一天”，是一种状态 ——世界在里面继续运转，只是”买入”这一个动作被禁。
continue把这天所有其他路径抹掉
4.2 第三例副作用死刑：i-2 过严——禁令写错了地方
状态分裂对了（hold/justSold/free），但把 free 的转移写成 justSold[i-2]——直觉”冷冻几天解禁差几格”，账算错了：
1
2
3
4
规则：卖出 d → d+1 冷冻 → d+2 可买 （冷冻 1 天）
i-1 填法：justSold[d] → free[d+1] → hold[d+2] ✓ 恰好
i-2 填法：justSold[d] → free[d+2] → hold[d+3] ✗ 多冻一天，路径丢失
病根是把禁令写进了状态定义（free = “空仓且可买 ”）。正确的语义：free = 空仓（冷冻日也是空仓——你确实一股没有，只是今天不能买） ；”不能买”的禁令只写在一条转移边上——hold 的买入只能从 free[i-1] 来，不能从 justSold[i-1] 直接来。两个”差一格”的转移拼出恰好一天的冷冻：
1
2
3
4
justSold[i-1] → free[i] → hold[i+1]
第 i-1 天卖出 第 i 天空仓 第 i+1 天买入
（冷冻日，在 free 里躺着）
状态机的禁令永远写在转移边上，不写在状态定义里 ——状态只描述”我是谁”，禁令描述”我能去哪”。
4.3 0 元照妖镜与”不动”分支的收官
hold[3] 这格连错三轮：写 0，正确 1。0 的来源是 -prices[3] = -0 = 0（121 旧转移），正确是 free[2]-prices[3] = 1-0 = 1。0 元买入是照妖镜 ：买入价非 0 时两种写法只差一个常数，错误能藏很久；买入价 0 时，一个等于 0、一个等于全部本金，藏无可藏。物理画面一句话钉死：口袋里的钱不会因为买了 0 元的股票就蒸发 。
最后一格 hold[4] = max(1, 0) = 1——只算”今天买入”（0）没和”继续持有”（1）取 max。“不动”分支在 121/122/309/188/714 五道题里现身五次 ，从 121 的 cash 行一路打到 309 的最后一格——它是这个家族真正的 BOSS，也是所有 max 转移的左半边。自查口诀的最终版：写 max 之前先问：左半边（不动/继承）你带了吗 。
5. LC714：改一个常数——一分钟的题
每笔交易收 fee 手续费。
[1,3,2,8,4,9], fee=2→ 8。
122 状态机原样保留，卖出边减 fee：
1
2
cash[i] = max(cash[i-1], hold[i]+prices[i]-fee)
这题的价值全在两个思考题：
- 等价性 ：fee 扣在买入边和卖出边等价 ——fee 是一笔交易的过路费，一进一出只收一次，收在入口还是出口总账相同；区别只是持仓中的 hold 平移一个 fee，而答案取自 cash（空仓），平移不外泄。钱在完整交易的两端守恒，中间的记账口径不影响终点
- 手续费的语义 ：
[1,3,7,5,10,3], fee=3一笔 1→10 拿 6，拆两笔只有 5——fee 抑制交易次数 ；[9,8,7,1,2]赚 1 付 3，不交易——max 的”不动”分支兜底
手推表最后一格 hold[5] 又凑了一次（写 10 应 1，且 cash[5]=8 暴露实际按 1 算）——”只推答案行”的第四次现身。
6. 股票家族总表：五个限制，五种改动
| 题 | 限制 | 状态机改动 | 新增教训 |
|---|---|---|---|
| 121 | 只许一次 | hold/cash 双态基础 | “不动”分支首现 |
| 122 | 无限次 | 改一条转移 （本金从 cash 流动） | 传钱通道；落袋贪死刑 |
| 188 | 最多 k 次 | 加一维 （j = 层数，一层一次交易） | 不可能状态哨兵；j=0 地基要活算 |
| 309 | 冷冻期 | 加一个状态 （cash 分裂出 justSold） | 禁令写在边上；跳天生死刑 |
| 714 | 手续费 | 改一个常数 （卖出边 -fee） | 等价性 = 钱在交易两端守恒 |
三例副作用死刑（同一个元模式的三个马甲）：
1
2
3
4
落袋贪生（122）：浮盈就清零 + 原价重建仓 —— 数不了次数，违反冷冻
跳天生（309）：sale 标记 + continue 跳天 —— 贪心丢路径，世界被饿死
改对迁就错（188 手推）：把正确的 sold 改坏去匹配错误的 hold —— 拆报警器
共同死因：用运行时副作用/表面自洽模拟状态与正确性，而不是把状态和禁令写进结构里 。
7. 方法论增补
| 问题 | 判据 | 出处 |
|---|---|---|
| 一维装不下时 | 问”同一天结束时有几种处境”——处境数 = 状态数 | 121 |
| 限制怎么进模型 | 加一维（次数）/ 加一状态（冷冻）/ 改一常数（费率）/ 改一下标（解禁延迟） | 家族总表 |
| 禁令写在哪 | 转移边上，永远不在状态定义里 | 309 |
| 买入分支的本金 | 口袋全部现金（cash[i-1]-prices[i]），0 元买入是照妖镜 | 122/309/188 |
| 不可能状态 | max 世界用 -MaxInt（小而无害），填 0 = 凭空本金 | 188 |
| 答案位置 | 多状态时取相关状态的 max（max over j、max(free, justSold)） | 188/309 |
| 手推纪律 | 每层写满对齐；每格标注 max 哪边赢；残骸必须删干净 | 188 七轮表 |
| 矛盾怎么办 | 矛盾是报警器——改错的一边去对齐对的，绝不反过来 | 188 |
8. 终章预告：LC140
第 6 级（最后一站）：LC140 单词拆分 II ——回溯期亲手数过 417 万次调用、缓存候选词列表”一个数字都没差”、以及”缓存结论不缓存选择”的判据，全部在此合龙。它是 DP 和回溯的合体：DP 负责判断哪些路活着（可行性折叠），回溯负责把活路走完（方案枚举） ——两个系列在此闭环。
总结
五道题，一条主线，三个感想：
状态机是”我是谁”的建模学 。每道题的转移大同小异，真正的设计全在”今天结束时我处于什么状态”——持仓与否（121）、完成几笔（188）、是否刚卖（309）。限制从来不是障碍，是状态的提示：每种限制都精确对应一种结构改动 （一维/一状态/一常数），这是本篇唯一需要背的表。
“不动”是这个家族的 BOSS 。五道题、五次现身、三种形态（继承/继续持有/不交易）——它永远是 max 的左半边，永远最容易被忘掉，永远在 0 元买入、全程下跌这种边界格子里现形。口诀贴显示器：写 max 之前先问，左半边带了吗 。
188 那张七轮表比五道题都值钱 。残骸复制、串层、改对迁就错、只推答案行——四种错误模式在一张表里集齐，每种都配了完整的一生。它最终教会的是一件事：打补丁修复不了系统性混乱，重画（对着机器打印誊写 + 逐格标注）才能清零 。手推表和代码是同一张图纸的两份拷贝，图纸乱了，找机器要一份新的。
终章 140 见——从 IP 题到单词拆分 II，从决策树到状态机，正好一个圆。
参考资料
- LeetCode 121. 买卖股票的最佳时机
- LeetCode 122. 买卖股票的最佳时机 II
- LeetCode 188. 买卖股票的最佳时机 IV
- LeetCode 309. 最佳买卖股票时机含冷冻期
- LeetCode 714. 买卖股票的最佳时机含手续费
- 动态规划第五篇：区间DP——从看什么都像背包到最后戳谁
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。