动态规划（Dynamic Programming, DP）详解¶
一句话：动态规划是一种把复杂问题拆成子问题、把子问题的解保存起来再复用，从而避免重复计算、提高效率的算法思想。
常见场景：最短路径、背包问题、字符串编辑、组合计数、树/图相关计算、最优子结构问题等。
1. 何为动态规划？¶
| 关键概念 | 说明 |
|---|---|
| 最优子结构 | 目标问题的最优解可以由其子问题的最优解构成。 |
| 重叠子问题 | 在递归求解过程中，同一子问题会被多次重复计算。 |
| 状态（State） | 子问题的具体描述，一般用一组变量（索引、剩余量、前缀/后缀等）来表示。 |
| 状态转移方程（Transition） | 用已知状态求解新状态的递推公式。 |
| 记忆化（Memoization） | 递归+缓存（Top‑Down）。 |
| 表格法（Tabulation） | 迭代填表（Bottom‑Up）。 |
典型的 递归 + 缓存 与 迭代填表 两种实现方式，选择时取决于问题特点与可读性。
2. DP 解决流程¶
-
确定问题类型
- 是否满足最优子结构？
- 是否有重叠子问题？ -
设计状态
- 只保留足够描述子问题所需的变量。
- 例：dp[i]（前i个元素的最优解）、dp[i][j]（前i个元素且剩余j资源的最优解）等。 -
确定状态转移方程
- 推导出dp[...]=之前状态的组合。
- 常见形式：dp[i] = max(dp[i-1] + a[i], dp[i-2] + a[i])、dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])等
。 -
设定边界/初始值
- 例如dp[0] = 0、dp[negative] = -∞等。
- 注意是否需要多行/多列的初值。 -
迭代/递归求解
- 迭代时按状态的 “层级” 依次填表；
- 递归时用 memo 记录已求解状态。 -
取答案
- 最终答案往往是dp[n]或dp[n][*]的某个组合。 -
优化（可选）
- 空间压缩：只保留前一层/前一行。
- 时间压缩：使用滑动窗口、单调队列、分治优化、匀速扫描、KMP、FFT 等。
3. 常见 DP 模式¶
| 模式 | 典型例子 | 说明 |
|---|---|---|
| 1 维 DP | Fibonacci、背包 1D、爬楼梯、区间 DP 中的单维子区间 | 只需一个数组即可记录状态。 |
| 2 维 DP | 矩阵链乘、最短路径（Dijkstra+DP）、最长公共子序列、编辑距离 | 维度通常是索引或资源。 |
| 多维 DP | 多维背包、图的 DP、状态机 DP | 状态空间较大，需注意空间/时间。 |
| DP on Graph | DAG 的最长路径、最短路（Bellman-Ford）、图的遍历 | 通过拓扑排序或松弛法实现。 |
| DP on Tree | 计算树直径、树形 DP、树上最大子树 | 通过 DFS + 状态合并。 |
| 区间 DP | 最优二叉搜索树、石子合并、最优切割 | 对区间 [l,r] 递推。 |
| 位 DP | 子集问题、旅行商（TSP） | 用二进制掩码表示已选/未选。 |
| 字符串 DP | LCS、最短编辑距离、最长回文子串 | 对字符序列进行递推。 |
4. 经典动态规划问题与代码¶
代码示例均使用 Python 3，读者可以根据需要转译为 C++/Java 等。
4.1 斐波那契（Fibonacci）¶
def fib(n):
if n <= 1:
return n
dp = [0] * (n+1)
dp[0], dp[1] = 0, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
4.2 01 背包（0/1 Knapsack）¶
def knapsack_01(weights, values, W):
n = len(weights)
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
w, v = weights[i-1], values[i-1]
for j in range(W+1):
dp[i][j] = dp[i-1][j] # 不选
if j >= w:
dp[i][j] = max(dp[i][j], dp[i-1][j-w] + v) # 选
return dp[n][W]
4.3 完全背包（Unbounded Knapsack）¶
def knapsack_unbounded(weights, values, W):
dp = [0]*(W+1)
for w, v in zip(weights, values):
for j in range(w, W+1):
dp[j] = max(dp[j], dp[j-w] + v)
return dp[W]
4.4 最长公共子序列（LCS）¶
def lcs(s, t):
n, m = len(s), len(t)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
if s[i-1] == t[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[n][m]
4.5 最短编辑距离（Levenshtein Distance）¶
def edit_distance(s, t):
n, m = len(s), len(t)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(n+1): dp[i][0] = i
for j in range(m+1): dp[0][j] = j
for i in range(1, n+1):
for j in range(1, m+1):
if s[i-1] == t[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
return dp[n][m]
4.6 最短路径（DAG）¶
def dag_shortest_path(graph, source):
# graph: dict(node -> list[(to, weight)])
# 先拓扑排序
from collections import defaultdict, deque
indeg = defaultdict(int)
for u, edges in graph.items():
for v, w in edges:
indeg[v] += 1
q = deque([u for u in graph if indeg[u]==0])
topo = []
while q:
u = q.popleft()
topo.append(u)
for v, _ in graph[u]:
indeg[v] -= 1
if indeg[v]==0: q.append(v)
INF = float('inf')
dist = defaultdict(lambda: INF)
dist[source] = 0
for u in topo:
if dist[u]==INF: continue
for v, w in graph[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
return dist
4.7 树形 DP（计算树直径）¶
def tree_diameter(adj):
# adj: list of neighbors for each node
n = len(adj)
def dfs(u, parent):
max1 = max2 = 0 # 两条最长的子树深度
for v in adj[u]:
if v == parent: continue
d = dfs(v, u) + 1
if d > max1:
max2 = max1
max1 = d
elif d > max2:
max2 = d
nonlocal diameter
diameter = max(diameter, max1 + max2)
return max1
diameter = 0
dfs(0, -1)
return diameter
4.8 位 DP（旅行商 TSP 简易版本）¶
def tsp_tsp(cost):
# cost: NxN matrix
n = len(cost)
dp = [[float('inf')]*n for _ in range(1<<n)]
dp[1][0] = 0 # 只访问起点
for mask in range(1, 1<<n):
for u in range(n):
if not (mask & (1<<u)): continue
for v in range(n):
if mask & (1<<v): continue
new_mask = mask | (1<<v)
dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + cost[u][v])
full = (1<<n) - 1
return min(dp[full][i] + cost[i][0] for i in range(n))
5. DP 优化技巧¶
| 优化手段 | 适用场景 | 关键点 |
|---|---|---|
| 空间压缩 | 只需要上一层状态 | 例如 01 背包可以用一维数组；树形 DP 只保留子树的 DP 结果 |
| 单调队列/滑动窗口 | 子序列最长递增/最长子段 | 通过队列维护窗口内的最大值/最小值 |
| 分治 DP (Divide & Conquer Optimization) | 递推式满足 opt[i][j] ≤ opt[i][j+1] |
递推时只需搜索 opt 范围 |
| Knuth 优化 | 递推式满足 opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j] |
适用于区间 DP 如 矩阵链乘、`最优二叉搜 |
| 索树` | ||
| BIT / Fenwick / Segment Tree | 需要在区间内做点更新、区间查询 | 用于 最大子数组和、子序列计数 |
| FFT / NTT | 多项式卷积 | 用于计算组合数、区间 DP 的快速合并 |
| bitmask + DP + subset sum | 子集求和、TSP | 通过预处理快速访问子集的 DP |
注意：在做优化前先确保理解 DP 的基本正确性；过早的优化可能导致实现错误。
6. 常见错误与调试技巧¶
| 错误 | 症状 | 对策 |
|---|---|---|
| 状态定义错误 | 结果不符合预期或超时 | 仔细检查 dp 的含义，确认是否真的能覆盖所有子问题 |
| 边界值漏写 | 某些输入导致数组越界或结果为 0 |
先写清晰的初始化，尤其是 dp[0]、dp[neg]、dp[inf] |
| 双重计数/漏计 | 计数类问题出现重复/漏解 | 用 dp[i][j] 结构或 bitmask 明确状态之间的转换 |
| 时间复杂度误判 | 认为 O(n²) 但实际是 O(n³) | 仔细算一下循环层数，特别是嵌套循环、递归深度 |
| 使用错误的比较符号 | 最大化/最小化时使用 > / < 逆 |
先写 best = -INF 或 INF，再 max/min |
| 无效的记忆化键 | memo[(i,j)] 只缓存一次 |
若递归参数多，最好用 lru_cache 或 dp 表 |
调试建议：先跑小规模手工测试，用
print(dp)打印中间表格；在 CF、LeetCode 等平台上可开启debug打印。若出现
RuntimeError: maximum recursion depth exceeded，考虑改为表格法或增加递归栈深度。
7. 学习路径建议¶
| 阶段 | 目标 | 推荐资源 |
|---|---|---|
| 入门 | 理解 DP 的核心思想，能手写几道经典题 | 《动态规划（算法导论）》、LeetCode 经典 100+ DP 题 |
| 进阶 | 掌握 DP 优化技巧（空间压缩、分治、Knuth） | 《剑指Offer 第2版》、《算法竞赛进阶指南》 |
| 应用 | 在实际项目或竞赛中快速构建 DP 模块 | 竞赛代码库、Codeforces、AtCoder DP 区域 |
| 深造 | 研究 DP 在图论、组合数学中的深层理论 | 《组合数学》、ACM ICPC 参考手册、论文阅读 |
练习时可以先用递归+缓存写，确认正确后再改写为表格法；两种实现对比能帮助你更好地理解状态与转移。
8. 小结¶
- 动态规划 通过“把复杂问题拆成子问题、保存子问题结果”来降低时间复杂度。
- 核心步骤：确认最优子结构、定义状态、写转移方程、设边界、填表/递归、取答案。
- 典型模式：1D、2D DP、树/图 DP、区间 DP、位 DP、字符串 DP。
- 技巧：空间压缩、分治优化、Knuth 优化、单调队列、FFT、BIT 等。
- 常见陷阱：状态定义错误、边界漏写、重复计数、错误比较符号、递归深度。
掌握了上述框架后，你可以针对任何需要“最优子结构 + 重叠子问题”的问题，快速想到是否可以用 DP。多练习，多做总结，DP
的思路会越来越自然。