动态规划套路模板
动态规划的状态定义与转移方程推导见 动态规划：状态定义与转移方程。本文是套路分类 + 模板代码的速查手册——看到题目先归类到某种 DP，直接套模板改条件。
一、DP 套路总览
面试中 90% 的 DP 题落在五类套路里：
| 套路 | 识别信号 | 状态形态 | 典型题 |
|---|---|---|---|
| 线性 DP | 一维序列、单方向递推 | dp[i] | 爬楼梯、打家劫舍、LIS |
| 区间 DP | 取/合并一段区间 | dp[i][j]（i<j） | 合并石子、回文子序列 |
| 背包 | 容量 + 物品选或不选 | dp[j] 容量维度 | 分割等和子集、零钱兑换 |
| 树形 DP | 树、父子依赖、选/不选 | dp[node] | 打家劫舍 III、树的直径 |
| 状态压缩 DP | n≤20 的集合/子集 | dp[mask] | 旅行商、划分集合 |
拿到题先问自己：数据规模多少？一维还是二维？转移依赖前一个、前一行还是整棵子树？
二、线性 DP 模板
模板 1：一维顺推（dp[i] 依赖 dp[i-1]/dp[i-2]）
def linear_dp_template(arr):
n = len(arr)
dp = [0] * n
dp[0] = arr[0] # 初始化
for i in range(1, n):
dp[i] = max(dp[i - 1], dp[i - 2] + arr[i]) # 替换成具体转移
return dp[n - 1]
模板 2：LIS 的 O(n log n) 贪心二分（LC 300）
def length_of_lis(nums):
tails = [] # tails[k] = 长度为 k+1 的递增子序列最小末尾
for num in nums:
left, right = 0, len(tails)
while left < right: # 找第一个 >= num 的位置
mid = (left + right) // 2
if tails[mid] < num:
left = mid + 1
else:
right = mid
if left == len(tails):
tails.append(num)
else:
tails[left] = num
return len(tails)
套路要点：求个数/方案数多用顺推；求最长/最大常考虑二分维护单调序列；一维 DP 依赖前两个状态时滚动数组压缩到 O(1)。
三、区间 DP 模板
区间 DP 的状态是 dp[i][j] 表示区间 [i, j] 的最优值，转移时枚举区间内最后一个分割点 k。遍历顺序必须是长度从小到大。
def interval_dp_template(nums):
n = len(nums)
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1): # 枚举区间长度
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j): # 枚举分割点
dp[i][j] = min(dp[i][j],
dp[i][k] + dp[k + 1][j] + cost(i, k, j))
return dp[0][n - 1]
例题：最长回文子序列（LC 516）
def longest_palindrome_subseq(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n - 1, -1, -1): # 注意倒序填表
dp[i][i] = 1
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]
套路要点：
- 遍历顺序：外层长度，内层左端点，保证依赖的子区间已算。
- 环形的区间 DP（如破环成链）常把数组复制一份（2n）处理。
- 优化：四边形不等式可把 O(n³) 降到 O(n²)，面试提一句即可，不必实现。
四、背包问题模板
背包的本质：dp[j] = 容量为 j 时的最优值，对每个物品更新一维数组。
01 背包（每个物品最多一次，倒序遍历）
def knapsack_01(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for j in range(capacity, weights[i] - 1, -1): # 倒序防重复
dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
return dp[capacity]
完全背包（每个物品无限次，正序遍历）
def knapsack_complete(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for j in range(weights[i], capacity + 1): # 正序允许重复
dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
return dp[capacity]
多重背包（每个物品有限次，二进制拆分）
def knapsack_multi(weights, values, counts, capacity):
# 二进制拆分：把 count 拆成 1,2,4,... 后当作 01 背包
new_weights, new_values = [], []
for w, v, c in zip(weights, values, counts):
k = 1
while k <= c:
new_weights.append(w * k)
new_values.append(v * k)
c -= k
k <<= 1
if c > 0:
new_weights.append(w * c)
new_values.append(v * c)
return knapsack_01(new_weights, new_values, capacity)
套路要点：
- 倒序 = 01，正序 = 完全，一句话记住。
- 求方案数时把
max换成+（如 LC 518 零钱兑换 II）。 - 问「能否凑出目标」用布尔 DP（LC 416 分割等和子集）。
- 多维限制（重量+体积）就把
dp[j]变成dp[j][k]，复杂度随之升一维。
五、树形 DP 模板
树形 DP 用后序遍历（先算子树，再合并到父节点），转移发生在父子之间。模板：
def tree_dp_template(root):
def dfs(node):
if not node:
return 0
left = dfs(node.left) # 先递归子节点
right = dfs(node.right)
# 合并：选/不选、累加、取最大等
return merge(left, right, node.val)
return dfs(root)
例题：打家劫舍 III（LC 337，选/不选两态）
def rob(root):
def dfs(node):
if not node:
return [0, 0] # [不抢该节点, 抢该节点]
l = dfs(node.left)
r = dfs(node.right)
not_rob = max(l) + max(r) # 不抢：子树随便
rob = node.val + l[0] + r[0] # 抢：子树不能抢
return [not_rob, rob]
return max(dfs(root))
树的直径（LC 543/124，后序累加最值）
def diameter(root):
ans = 0
def depth(node):
nonlocal ans
if not node:
return 0
left = depth(node.left)
right = depth(node.right)
ans = max(ans, left + right) # 经过该节点的最长路径
return max(left, right) + 1
depth(root)
return ans
套路要点：
- 返回值只带单方向信息（深度、最大值），全局答案用闭包变量记录。
- 「每个节点选或不选」两态是树形 DP 最常见的形态（打家劫舍 III、监控二叉树 LC 968）。
六、状态压缩 DP 模板
当数据规模 n ≤ 20 且状态是「集合选择」，用 mask 二进制位表示已选元素。dp[mask] = 状态 mask 下的最优值。
枚举子集模板
dp = [float('inf')] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
# 枚举 mask 的子集 sub：转移依赖子集
sub = mask
while sub:
# 用 dp[mask ^ sub] + cost(sub) 更新 dp[mask]
sub = (sub - 1) & mask
例题：TSP 最短回路
# dp[mask][i]：已访问 mask，当前在 i 的最短距离
dp = [[float('inf')] * n for _ in range(1 << n)]
dp[1 << 0][0] = 0
for mask in range(1 << n):
for i in range(n):
if not (mask >> i) & 1:
continue
for j in range(n):
if (mask >> j) & 1:
continue
dp[mask | (1 << j)][j] = min(
dp[mask | (1 << j)][j], dp[mask][i] + dist[i][j])
套路要点：
n的位数就是状态数上限——超过 20 就基本告别状压。- 枚举子集
sub = (sub-1) & mask的均摊复杂度 O(3^n)。 - 配合记忆化搜索写起来更直观：
f(mask, last)递归 +lru_cache。
七、复杂度与优化速查
| 套路 | 朴素复杂度 | 常见优化 |
|---|---|---|
| 线性 DP | O(n) / O(n log n) | 滚动数组 → O(1) 空间 |
| 区间 DP | O(n³) | 四边形不等式 → O(n²) |
| 01/完全背包 | O(n × capacity) | 一维滚动数组 |
| 多重背包 | O(n × capacity × count) | 二进制拆分 |
| 树形 DP | O(n) | — |
| 状态压缩 DP | O(n² · 2ⁿ) | 记忆化搜索、子集枚举优化 |
八、常见问题
Q: 怎么快速判断用哪种 DP 套路？
看状态维度与依赖方向：一维数组且依赖相邻位置 → 线性；区间上做合并/分割 → 区间；有容量上限做选择 → 背包；树结构上自底向上 → 树形；数据规模小到能枚举集合 → 状压。
Q: 倒序遍历和正序遍历的背诵口诀？
「01 背包倒着填，完全背包正着填」。倒序保证每个物品只被使用一次，正序允许无限复用。
Q: 套路模板直接背，面试够用吗？
模板负责加速，但状态定义与转移必须现场推导。建议每个套路配 2-3 道例题练到能独立写出模板，再谈优化。
Q: 空间优化优先级？
先保证正确，再滚动数组；只有明确分析出依赖关系后才压缩，压缩错误比超空间更致命。
相关文章：
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。