动态规划

2026-06-02

DP = 子问题 + 不重复计算。把指数级搜索压成多项式，全靠”算过的别再算”。

直觉 — 子问题不重复

DP 本质上就两步，背下来：

  1. 状态定义：dp[i][j] 表示”前 i 个 / 前 j 个” 的某个性质（长度、个数、是否可行、最值）。状态定对了，题就做完了一半。
  2. 转移方程：当前 dp[i][j] 怎么从更小的子问题拼出来。

能用 DP 的两个标志：

  • 最优子结构：大问题的最优解，由小问题的最优解组合得到。
  • 无后效性：当前状态确定后，后面怎么走和”之前是怎么走到这”无关。

两种写法等价，挑顺手的：

  • 记忆化递归（自顶向下）：写法接近暴搜，加个 @cache 就成 DP。不用想遍历顺序，只算访问到的子问题。
  • 迭代填表（自底向上）：先算小的再算大的，循环顺序就是依赖顺序。没有递归栈，方便空间优化。

下面动画用 "ABCDE" vs "ACE" 逐格填 LCS 表，绿色是当前格、半透明绿是它依赖的左、上、左上三个格；下半部分把 0/1 背包（倒序）和完全背包（正序）放在一组数据上对比。看动画时盯一件事：当前格的值，永远只来自已经填好的格子 —— 这就是”无后效性”。

三种范式

记住三个原型题，90% 的 DP 都是它们的变种。

线性 DP — 爬楼梯型

状态只依赖前面有限个位置。一维数组够用。

1
2
3
# 70. 爬楼梯
dp[i] = dp[i-1] + dp[i-2]
# dp[0] = dp[1] = 1

同款套路：打家劫舍（dp[i] = max(dp[i-1], dp[i-2]+nums[i])）、最大子数组、最小路径和。

LIS — 序列里挑子序列

dp[i] = 以 nums[i] 结尾的最长递增子序列长度。注意是”以 i 结尾”，不是”前 i 个”，否则转移写不出来。

1
2
3
4
5
6
7
# O(n^2)
for i in range(n):
    dp[i] = 1
    for j in range(i):
        if nums[j] < nums[i]:
            dp[i] = max(dp[i], dp[j] + 1)
ans = max(dp)

还有 的贪心+二分（维护 tails 单调数组，二分插入），面试两种都要会。

背包 — 多阶段决策

每个物品”选不选 / 选几次”，是 DP 里最高频的范式。

LCS / 编辑距离也属于这一类（”当前字符匹/不匹”是两阶段决策）：

1
2
3
4
5
6
7
8
9
10
11
12
13
# 1143. LCS
if text1[i-1] == text2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

# 72. 编辑距离
if word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = 1 + min(dp[i-1][j],    # 删除
                       dp[i][j-1],    # 插入
                       dp[i-1][j-1])  # 替换

0/1 背包：每个物品至多用一次。一维优化 → 容量倒序。

1
2
3
for i in range(n):
    for j in range(W, w[i]-1, -1):   # 倒序!
        dp[j] = max(dp[j], dp[j-w[i]] + v[i])

完全背包：每个物品用任意次。一维优化 → 容量正序。

1
2
3
for i in range(n):
    for j in range(w[i], W+1):       # 正序!
        dp[j] = max(dp[j], dp[j-w[i]] + v[i])

背包变形对照表（动画里能看到两种顺序的差别）：

问题 初始化 转移
最大价值 dp = [0]*(W+1) dp[j] = max(dp[j], dp[j-w]+v)
方案数 dp[0]=1, 其余 0 dp[j] += dp[j-w]
能否装满 dp[0]=True dp[j] = dp[j] or dp[j-w]
组合 vs 排列 — 物品外层 = 组合；容量外层 = 排列

模板 — Python

记忆化递归（最不易错）：

1
2
3
4
5
6
7
8
9
10
11
12
from functools import cache

@cache
def dfs(i, j):
    if i == 0 or j == 0:
        return 0
    if text1[i-1] == text2[j-1]:
        return dfs(i-1, j-1) + 1
    return max(dfs(i-1, j), dfs(i, j-1))

ans = dfs(m, n)
dfs.cache_clear()   # 多组数据时记得清

迭代填表（无栈风险、易压空间）：

1
2
3
4
5
6
7
8
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
    for j in range(1, n+1):
        if text1[i-1] == text2[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
ans = dp[m][n]

空间优化 — 滚动数组

如果 dp[i][...] 只依赖 dp[i-1][...]，就只留两行甚至一行。

二维 → 两行（依赖上一行）：

1
2
3
4
5
6
prev = [0]*(n+1)
for i in range(1, m+1):
    cur = [0]*(n+1)
    for j in range(1, n+1):
        ...
    prev = cur

二维 → 一行（背包套路，靠遍历顺序保证语义）：

  • 0/1 背包：j 倒序，引用的 dp[j-w] 还是上一轮的值（”i 没选过”）。
  • 完全背包：j 正序，引用的 dp[j-w] 已经是本轮更新过的（”i 可以反复选”）。

顺序错了，物品就被选了多次或一次都没选。这是背包最高频的 bug。

记忆法 / 易错点

三句口诀：

  • 状态先定义，转移再写式。
  • 边界要写全，顺序要对路。
  • 一维滚一滚，01 倒、完全正。

常踩的坑：

  • 下标错位：状态 dp[i] 用”前 i 个” → 数组取 s[i-1]，别取 s[i]。
  • 初始化漏边界：求方案数时 dp[0]=1（空集算一种）；求最值时初始化要和 max/min 方向一致。
  • LIS 状态写错：必须是”以 i 结尾”，不能是”前 i 个里的”，否则无法转移。
  • 背包顺序：倒序 / 正序与”物品/容量谁在外层”，是两个独立维度，别混。
  • 记忆化清缓存：@cache 在多组测试里会串数据，函数返回前 cache_clear()。

思考题

Q1：为什么 0/1 背包容量要倒序？正序会怎样？

正序时，dp[j-w[i]] 可能已经在本轮被更新过，相当于物品 i 被用了多次 —— 那是完全背包。倒序保证 dp[j-w[i]] 还是”上一轮 i 没选时”的值。

Q2：记忆化递归 vs 迭代 DP 怎么选？

写起来怕错 → 记忆化递归（不用想顺序、只算需要的子问题）。要压空间 / 数据规模大 → 迭代填表（无栈风险，方便滚动数组）。Python 默认递归深度 1000，深状态记得 sys.setrecursionlimit。

Q3：背包里"组合"和"排列"为什么遍历顺序不同？

物品外层：每个物品按固定顺序考虑，(1,2) 和 (2,1) 只算一种 = 组合。容量外层：每个容量都把所有物品扫一遍，同一组物品可以以不同顺序出现 = 排列。

LeetCode 练习

热身：70. 爬楼梯、198. 打家劫舍、53. 最大子数组、300. LIS、322. 零钱兑换

进阶：1143. LCS、72. 编辑距离、416. 分割等和子集、494. 目标和、518. 零钱兑换 II