动态规划 (DP)

一句话

DP 不是技巧, 是一个关于"重叠子问题 + 最优子结构 + 无后效性"的数学结构. 一旦看清楚三个判断条件, 一道题拿本子画 5 分钟就能定下状态转移. 大多数人写不出 DP 都因为跳过了第 1 步: 精确定义状态.

三个判断

子问题重叠: 不同递归路径会重复计算同样的子问题.
最优子结构: 原问题的最优解由子问题最优解组合而成.
无后效性: 未来决策只依赖当前的状态而不依赖历史路径细节.

模板 5 步

定义状态 dp[i][j] 的精确含义;
写出转移方程 dp[i][j] = ...dp[i'][j']...;
设定初始 / 边界条件;
决定计算顺序: 拓扑序 or 递归 + memo;
还原方案: 从终态回溯路径.

tip

困难不在写代码, 而在第 1 步—精确定义状态常常是题目里能不能解出的关键. 别图省事定多状态: 能用 (i, j) 就别上 (i, j, k, …).

三大经典原型

1. 背包

类型	状态转移
0/1 背包	`dp[i][w] = max(dp[i-1][w], dp[i-1][w-vi] + vi)`
完全背包	`dp[i][w] = max(dp[i-1][w], dp[i][w-vi] + vi)` 同一 i 可取多次
多重背包	二进制拆点优化
分组背包	同组任选一个

空间优化: 0/1 用 1D 倒序遍历; 完全使用 1D 正序.

2. LIS / LCS

LIS O(n²), 二分加速 O(n log n):

tails[k] = 当前已知长度为 k+1 的 LIS 末尾最小值
插入 x 时: bisect_left(tails, x), 替换或扩展

LCS O(n·m): dp[i][j] = dp[i-1][j-1] + 1 if a[i]==b[j] else max(dp[i-1][j], dp[i][j-1]).

3. 区间 DP

for len = 1..n:
  for i = 0..n-len:
    j = i + len - 1
    for k = i..j-1:
      dp[i][j] = combine(dp[i][k], dp[k+1][j], cost(i,j,k))

经典: 石子合并、矩阵链乘、戳气球 (LC 312).

状态压缩 DP

适用于状态空间小但树形多重集合 (n ≤ 20). 用 int 的位表示集合.

@cache
def dp(mask):
    if mask == target: return 0
    best = inf
    for i in range(n):
        if mask & (1 << i) == 0 and canUse(i, mask):
            best = min(best, dp(mask | (1 << i)) + cost(i))
    return best

LC 187 重复 DNA 序列、LC 1655 分配重复整数、TSP (LC 943).

经典题

LC 70 爬楼梯 (最入门);
LC 64 最小路径和;
LC 300 LIS、LC 1143 LCS;
LC 322 零钱兑换 (完全背包);
LC 312 戳气球 (区间 DP / 记忆化);
LC 5 最长回文子串 (中心扩展 vs Manacher);
LC 115 不同的子序列;
LC 32 最长有效括号.

易错

维度开得多 / 转移漏一种: 状态设计先在自己脑子里跑两遍.
依赖图错了: 把依赖必须在大小上呈现出来.
初始化语义错: dp[0] 表示 0 个物品 / 空间 / 边界, 常被误设.
没想清输出: 是 dp[终态], 还是要回看 max dp[*]? 比如 LC 152 最大子数组乘积要回扫.
忽略求最小值时 INIT 为 0 — 用 inf 初始化.

多语言对比

DP 表达在语言之间本质相同, 但实现形式略有差异:

Python @cache 装饰器让"记忆化搜索"一气呵成;
TypeScript 函数式写法依赖闭包, 但缺 memo 装饰器, 需要自写;
C++ 用全局 vector<vector<int>>, 1D 后二维滚动;
Go 没内置 memo, 通常闭包 + 手写 map[state]result 也可以.

这种差异无关算法本身, 而是关于语言如何让你写出清晰的状态转移表达. 但这是后续"运行时语义"那章的伏笔.

Keyboard shortcuts

Computer Science Notes