动态规划

01 / 共享的机制

一张表格逐格填充自己 —— 每一格都由常数个更早的格子组合而来。递推关系因子模式而异, 但底层机制 —— 状态、转移、填表顺序 —— 是共通的。

02 / 一句话本质

每个下标处于一个小而固定的状态集合中的某一个, 并有明确的状态间转移规则。把状态机沿输入展开 —— DP 表中每个状态一行,每个位置一列。

题目含冷冻期的股票最大利润价格[1, 2, 3, 0, 2]

持有

卖出

休息

每天三种状态:held(持有股票)、sold(刚卖出 —— 明天进入冷冻期)、rest(不持有,可自由买入)。逐日填表。

步

0 / 14

正在填

—

来源

—

最大利润

—

0 / 14

价格

03 / 模式骨架

# 状态机 DP —— 跟踪每个状态随时间的变化dp[state][0] ← 每个状态的基线for i in 1..n−1:for each state:dp[state][i] ← 对所有合法的源状态 state' 取 max/min(dp[state'][i−1] + cost(state'→state, input[i]))return 在终止状态上取 max dp[state][n−1]# 冷冻期:状态 = held / sold / rest# held[i] = max(held[i−1], rest[i−1] − price[i])# sold[i] = held[i−1] + price[i]# rest[i] = max(rest[i−1], sold[i−1])

04 / 什么时候用这个模式

"有限模式"

每个位置的选择取决于当前所处的模式 —— 持有还是不持有、连续还是断开、剩余可交易次数。模式就是状态。

"转移约束"

某些动作从某些状态出发是非法的 —— 卖出后必须先休息再买、不能连续跳两个、必须交替。非法转移编码了题目的规则;合法转移则成为递推式。

"答案按终止状态求"

最终答案是位置 n − 1 上各终止状态之间的最优。常常是“不持有”—— 但有时题目要求“必须以状态 X 结束”,那就只读一行。

"状态数为小常数"

通常是 2–5 个状态。当状态数随输入增长(例如交易次数 k), DP 会多出一个维度,复杂度变为 O(N · k)。

05 / 常见坑

状态缺失或重叠。

如果你的状态没有干净地划分所有可能的位置,转移就会爆炸,递推式也会出现歧义。自检:任意时刻的每个合法位置都能被恰好分配到一个状态上吗?做不到就先精化状态集再写代码。

ii.

各状态的基线不对称。

每个状态都需要自己的第 0 天初值,而且很少全为零。对冷冻期问题,held[0] = -price[0](今天买入),而 sold[0] = rest[0] = 0(尚未交易)。基线处的差一会一路扩散到之后的每个格子。

iii.

状态之间存在隐藏耦合。

填 dp[B][i] 时读 dp[A][i-1] 是没问题的;但若读 dp[A][i](同一列)就会产生次序依赖:在第 i 天内, 必须先填 A 再填 B。务必先画出转移图, 再让内层循环顺序与之相符。

06 / 去 LeetCode 上练习

状态机 DP 家族的四道题。前三题在状态数和冷冻/手续费规则上变化; 第四题切换题型,状态从“位置”变为“连续选择”。

01Best Time with Cooldown— LC 309中等→02Best Time with Fee— LC 714中等→03Best Time IV— LC 188困难→04Paint House— LC 256中等→

— / 什么时候用哪个

一维线性

当下标 i 处的答案只依赖常数个更早的下标时使用。

打家劫舍 · 爬楼梯 · 最大子段和

二维网格

当状态由两个下标组成 —— 网格,或两条相互作用的序列。

最短路径 · LCS · 编辑距离

背包

当每个物品都触发一次选 / 不选决策、且有容量约束时使用。

子集和 · 找零 · 划分

区间

当状态是一个区间 (i, j)、答案由内部区间组合得出时使用。

回文 · 矩阵链 · 戳气球

状态机

当每个下标可以处于若干有限状态之一、且状态之间有明确的转移规则时使用。

股票 · 冷冻期 · 双状态