动态规划详解

动态规划详解.md
发布日期：2026年01月25日
文件：动态规划详解.md
最后修改：2026-01-25 11:06:26

动态规划（Dynamic Programming, DP）详解

一句话：动态规划是一种把复杂问题拆成子问题、把子问题的解保存起来再复用，从而避免重复计算、提高效率的算法思想。

常见场景：最短路径、背包问题、字符串编辑、组合计数、树/图相关计算、最优子结构问题等。

1. 何为动态规划？

关键概念 说明
最优子结构 目标问题的最优解可以由其子问题的最优解构成。
重叠子问题 在递归求解过程中，同一子问题会被多次重复计算。
状态（State） 子问题的具体描述，一般用一组变量（索引、剩余量、前缀/后缀等）来表示。
状态转移方程（Transition） 用已知状态求解新状态的递推公式。
记忆化（Memoization） 递归+缓存（Top‑Down）。
表格法（Tabulation） 迭代填表（Bottom‑Up）。

典型的 递归 + 缓存 与 迭代填表 两种实现方式，选择时取决于问题特点与可读性。

2. DP 解决流程

  1. 确定问题类型
    - 是否满足最优子结构？
    - 是否有重叠子问题？

  2. 设计状态
    - 只保留足够描述子问题所需的变量。
    - 例：dp[i]（前 i 个元素的最优解）、dp[i][j]（前 i 个元素且剩余 j 资源的最优解）等。

  3. 确定状态转移方程
    - 推导出 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]) 等
    。

  4. 设定边界/初始值
    - 例如 dp[0] = 0、dp[negative] = -∞ 等。
    - 注意是否需要多行/多列的初值。

  5. 迭代/递归求解
    - 迭代时按状态的 “层级” 依次填表；
    - 递归时用 memo 记录已求解状态。

  6. 取答案
    - 最终答案往往是 dp[n] 或 dp[n][*] 的某个组合。

  7. 优化（可选）
    - 空间压缩：只保留前一层/前一行。
    - 时间压缩：使用滑动窗口、单调队列、分治优化、匀速扫描、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
的思路会越来越自然。