《Hello 算法》动态规划章末总结详解：三大特征、背包问题族与编辑距离的递推与空间优化

2026-09-06 18:58:01作者：房伟宁

导读

本文基于 en/docs/chapter_dynamic_programming/summary.md（该章“Summary”一节）展开，系统梳理动态规划（Dynamic Programming）的三步方法论——重叠子问题、最优子结构、无后效性，并对 0-1 背包、完全背包、零钱兑换（I/II）与编辑距离逐一拆解状态定义、状态转移方程与空间优化的遍历顺序。同时结合本仓库多语言实现（以 Python 为主）给出可运行的源码佐证。读完本文，你将掌握判定一个组合优化问题是否适用 DP 的检查清单，并能独立推导背包族与编辑距离问题的递推关系与一维滚动数组写法。

一、动态规划的本质：分解子问题 + 消除重复计算

动态规划的核心思想是将原问题分解为若干子问题，并通过存储子问题的解避免重复计算，从而显著提升计算效率。这是 summary.md 给出的第一个关键结论，也是整个章节的方法论基石。

在不考虑时间约束的前提下，所有动态规划问题都可以用回溯（暴力搜索）求解——但这样做时递归树中会包含海量的重叠子问题，导致效率极低。解决办法是引入记忆化（memo）列表，把已计算过的子问题解缓存起来，保证每个重叠子问题只被计算一次。

本仓库中每道 DP 题都按“暴力搜索 → 记忆化搜索 → 动态规划 → 空间优化”四个版本编排源码，例如：

爬楼梯：climbing_stairs_backtrack.py、climbing_stairs_dfs.py、climbing_stairs_dfs_mem.py、climbing_stairs_dp.py；
0-1 背包：knapsack.py 中同时包含 knapsack_dfs、knapsack_dfs_mem、knapsack_dp、knapsack_dp_comp 四个函数；
编辑距离：edit_distance.py 亦如此。

记忆化与 DP 的对应关系：两种视角、同一种表格

记忆化搜索是自顶向下的递归解法（从问题规模 $n$ 一路递归到最小子问题），而动态规划则是自底向上的迭代解法，形式上类似“填表”。二者求解的递推关系完全相同，只是遍历方向相反。

由于递推过程中“当前状态往往只依赖少数局部状态”，我们可以消去 $d p$ 表的一个维度来降低空间复杂度。以爬楼梯为例（到达第 $n$ 阶的方案数， $d p [i] = d p [i - 1] + d p [i - 2]$ ）：

def climbing_stairs_dp(n: int) -> int:
    if n == 1 or n == 2:
        return n
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

def climbing_stairs_dp_comp(n: int) -> int:
    if n == 1 or n == 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b   # 只保留两个局部状态
    return b

可以看到，空间优化后的版本仅保留 $d p [i - 1]$ 与 $d p [i - 2]$ 两个变量，将 $O (n)$ 空间降为 $O (1)$ （完整代码见 climbing_stairs_dp.py）。

补充说明：子问题分解是一种通用的算法思想，在分治、动态规划与回溯三者的含义不同——分治的子问题通常相互独立、可并行求解；动态规划依赖重叠子问题与记忆化复用；回溯则强调穷举状态空间并剪枝。这一对比在 docs/chapter_divide_and_conquer/divide_and_conquer.md 与本章各篇正文中有完整论述。

二、判定 DP 适用性的三大特征

并非所有问题都适合用动态规划求解。summary.md 归纳出三个必须同时满足的特征：

1. 重叠子问题（Overlapping Subproblems）

递归树中存在大量被反复计算的子问题，这正是记忆化与 DP 能提速的前提。判断方法：画出暴力递归树，观察相同参数 $(i, j)$ 的节点是否重复出现。若子问题互不重叠，DP 退化为普通分治，无法获得额外收益。

2. 最优子结构（Optimal Substructure）

若原问题的最优解可由其子问题的最优解构造而来，则该问题具备最优子结构。这是写出状态转移方程的依据：先定义“状态”（ $d p$ 表的语义），再回答“当前状态如何由更小的状态递推得到”。

例如 0-1 背包中，对第 $i$ 个物品做“不放入 / 放入”两种决策后，剩余问题是规模更小的 $(i - 1, c)$ 或 $(i - 1, c - w_{i})$ ，二者都是“前 $i - 1$ 个物品”的同类子问题——最优子结构由此成立。

3. 无后效性（No Aftereffects）

无后效性指：给定某一状态后，其未来发展只与该状态本身有关，而与到达该状态的“历史路径”无关。

需要特别警惕的是：很多组合优化问题不满足无后效性，因此无法用动态规划高效求解。比如后续章节的“N 皇后”等带全局约束的问题，状态历史会影响后续可行性判断，只能退回回溯等搜索方法（相关讨论见 docs/chapter_backtracking/backtracking_algorithm.md）。

从本仓库源码结构看，凡能进入 chapter_dynamic_programming 目录并通过“暴力 → 记忆化 → DP → 滚动数组”四件套实现的题目（完整清单），其共性都是同时满足上述三大特征。它们是检验自己理解的好样例。

三、背包问题族：从 0-1 背包到组合计数

背包问题是动态规划最典型的代表，其变体覆盖了 0-1 背包、完全背包与多重背包等。本章正文分别由 knapsack_problem.md、unbounded_knapsack_problem.md 讲解，以下按 summary 的脉络展开。

3.1 0-1 背包：为什么空间优化必须倒序遍历

状态定义： $d p [i] [c]$ 表示“在前 $i$ 个物品中选择，且背包容量为 $c$ 时能获得的最大价值”。对第 $i$ 个物品存在两种决策：

不放入：价值为 $d p [i - 1] [c]$ ；
放入（前提 $w_i \le c$ ）：价值为 $d p [i - 1] [c - w_{i}] + v_{i}$ 。

由此得到状态转移方程：

dp[i][c] = \max\big(dp[i-1][c],\ dp[i-1][c-w_i] + v_i\big)

仓库中的二维版本与一维滚动数组版本如下（knapsack.py）：

def knapsack_dp(wgt, val, cap):
    n = len(wgt)
    dp = [[0] * (cap + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for c in range(1, cap + 1):
            if wgt[i - 1] > c:
                dp[i][c] = dp[i - 1][c]                 # 超重，只能不选
            else:
                dp[i][c] = max(dp[i - 1][c],
                               dp[i - 1][c - wgt[i - 1]] + val[i - 1])
    return dp[n][cap]

def knapsack_dp_comp(wgt, val, cap):
    n = len(wgt)
    dp = [0] * (cap + 1)
    for i in range(1, n + 1):
        for c in range(cap, 0, -1):                     # 关键：倒序遍历
            if wgt[i - 1] <= c:
                dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
    return dp[cap]

为何必须倒序？ 空间优化后， $d p [c]$ 对应的递推来源是“正上方” $d p [i - 1] [c]$ 与“左上方” $d p [i - 1] [c - w_{i}]$ 。若容量 $c$ 从小到大正序遍历， $d p [c - w_{i}]$ 已被本轮更新成 $d p [i] [c - w_{i}]$ ，左上角状态被覆盖丢失，等价于允许同一物品被重复选取（变成完全背包语义）；因此必须让容量从大到小（倒序）遍历，保证读取到的永远是上一轮的 $dp[i-1][\cdot]$ 。

3.2 完全背包：无限次选取，正序遍历顺理成章

完全背包对每种物品的选取数量不设上限。当选择“放入一个第 $i$ 种物品”后，剩余子问题仍可在第 $i$ 种物品中继续选取，因此其递推来源是正上方与正左方：

dp[i][c] = \max\big(dp[i-1][c],\ dp[i][c-w_i] + v_i\big)

对比 3.1 可见差异仅在第二项的 $i$ （同一行）而非 $i - 1$ 。正因为依赖同一行左侧（即 $d p [i] [c - w_{i}]$ ），空间优化后恰好需要正序遍历——左侧更新的结果会被直接复用，形成“无限次选取”的效果。见 unbounded_knapsack.py：

def unbounded_knapsack_dp_comp(wgt, val, cap):
    n = len(wgt)
    dp = [0] * (cap + 1)
    for i in range(1, n + 1):
        for c in range(1, cap + 1):                     # 关键：正序遍历
            if wgt[i - 1] <= c:
                dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
    return dp[cap]

记忆锚点：0-1 背包倒序（防重复取用当前物品），完全背包正序（允许重复取用当前物品）。这个“正/倒序二分法”是背包族空间优化的灵魂。

3.3 零钱兑换 I：求“最少硬币数”，用哨兵表示无解

零钱兑换是完全背包的变体，发生了两处语义转换（coin_change.py）：

求“最大价值”变为求“最少硬币数”，方程中的 $\max()$ 相应改为 $\min()$ ；
从“不超过背包容量”变为“恰好凑出目标金额 $a m t$ ”，因此需要用 $a m t + 1$ 这一“足够大的哨兵”表示“无法凑出目标金额”的无效解。

dp[i][a] = \min\big(dp[i-1][a],\ dp[i][a-coins_i] + 1\big)

初始化时首行 dp[0][a] = MAX (a ≥ 1)，最终若 dp[n][amt] 仍等于 MAX 则返回 -1 表示无解；空间优化版本沿用完全背包的正序遍历，并令 dp[0] = 0 作为基准：

def coin_change_dp_comp(coins, amt):
    n = len(coins)
    MAX = amt + 1
    dp = [MAX] * (amt + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        for a in range(1, amt + 1):                     # 完全背包语义：正序
            if coins[i - 1] <= a:
                dp[a] = min(dp[a], dp[a - coins[i - 1]] + 1)
    return dp[amt] if dp[amt] != MAX else -1

3.4 零钱兑换 II：求“组合数量”， $\min$ 换成求和

零钱兑换 II 是求凑出目标金额的硬币组合数（而非最少硬币数），因此把“取较小值”变为“两类决策的方案数求和”（coin_change_ii.py）：

d p [i] [a] = d p [i - 1] [a] + d p [i] [a - c o i n s_{i}]

注意这里强调“组合”（每种组合只计一次），其正确性正是由“外层遍历硬币、内层遍历金额”的顺序保证的；初值 dp[i][0] = 1（金额为 0 时只有“什么都不选”一种方案）。空间优化后同样正序遍历：

def coin_change_ii_dp_comp(coins, amt):
    n = len(coins)
    dp = [0] * (amt + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        for a in range(1, amt + 1):                     # 正序
            if coins[i - 1] <= a:
                dp[a] = dp[a] + dp[a - coins[i - 1]]    # 求和而非取 min/max
    return dp[amt]

背包族变体速查表

问题	优化目标	状态来源	空间优化遍历顺序	无效解处理
0-1 背包	$\max$ 价值	正上方、左上	倒序	不选即可（价值 0）
完全背包	$\max$ 价值	正上方、正左	正序	不选即可（价值 0）
零钱兑换 I	$\min$ 硬币数	正上方、正左	正序	哨兵 $a m t + 1$ ，返回 $- 1$
零钱兑换 II	组合数求和	正上方、正左	正序	`dp[0]=1`，无解自然为 0

四种变体（含其余语言）均位于 codes/python/chapter_dynamic_programming 及各语言对应目录，可在本仓库中交叉比对以加深印象。

四、编辑距离（Levenshtein）：需要“左上角暂存变量”的第三类空间优化

4.1 问题定义与状态设计

编辑距离（又称 Levenshtein 距离）用于衡量两个字符串的相似度，定义为把一个字符串变成另一个字符串所需的最少编辑步数，其中编辑操作包含三种：插入、删除、替换。

状态定义： $d p [i] [j]$ 表示“将 $s$ 的前 $i$ 个字符变为 $t$ 的前 $j$ 个字符所需的最少编辑步数”。

4.2 状态转移方程

当 $s [i - 1] \neq t [j - 1]$ 时，有三个决策可选（edit_distance.py 中的二维 DP 版）：

插入：在 $s$ 尾部插入 $t [j - 1]$ ，对应剩余子问题 $d p [i] [j - 1]$ ；
删除：删除 $s [i - 1]$ ，对应 $d p [i - 1] [j]$ ；
替换：将 $s [i - 1]$ 替换为 $t [j - 1]$ ，对应 $d p [i - 1] [j - 1]$ 。

dp[i][j] = \min\big(dp[i][j-1],\ dp[i-1][j],\ dp[i-1][j-1]\big) + 1

而当 $s [i - 1] = t [j - 1]$ 时，两字符已经相等，无需对当前字符做任何编辑，直接继承左上角：

d p [i] [j] = d p [i - 1] [j - 1]

边界条件为首行首列：dp[i][0] = i（把 $s$ 的前 $i$ 个字符全部删除），dp[0][j] = j（在空串中依次插入 $t$ 的前 $j$ 个字符）。

4.3 空间优化：为什么“正序倒序都不行”，以及如何破局

编辑距离中 $d p [i] [j]$ 依赖正上方、正左方与左上角三个状态。压成一维后：

若倒序遍历，读到的 $d p [j - 1]$ 是本轮刚更新的 $d p [i] [j - 1]$ （正确），但左侧递推依赖的“正左方”实际上要的是 $d p [i] [j - 1]$ ，而左上角 $d p [i - 1] [j - 1]$ 却已被破坏；
若正序遍历，情况又反过来。

因此，单纯选择方向无法同时保住三个来源。仓库给出的解法是：用一个变量临时暂存左上角状态 leftup，每次迭代前先把将被覆盖的 $d p [j]$ 存入 temp，更新完 $d p [j]$ 后再把 temp 赋给 leftup 供下一格使用，从而等价转化为“可正序遍历”的情形（edit_distance.py）：

def edit_distance_dp_comp(s, t):
    n, m = len(s), len(t)
    dp = [0] * (m + 1)
    for j in range(1, m + 1):
        dp[j] = j                       # 初始化首行
    for i in range(1, n + 1):
        leftup = dp[0]                  # 暂存 dp[i-1][j-1]
        dp[0] += 1                      # 首列：相当于 dp[i][0] = i
        for j in range(1, m + 1):
            temp = dp[j]                # 先保存即将被覆盖的 dp[i-1][j]
            if s[i - 1] == t[j - 1]:
                dp[j] = leftup
            else:
                dp[j] = min(dp[j - 1], dp[j], leftup) + 1
            leftup = temp               # 移交给下一格的左上角
    return dp[m]

这段代码中 leftup 沿对角线“接力传递”的手法值得反复研读，是理解“DP 空间优化受依赖方向制约”的最佳案例。仓库驱动用例 s = "bag", t = "pack" 会同时输出暴力搜索、记忆化、DP 与空间优化四个版本的相同答案，可直接运行验证。正文完整推导见 edit_distance_problem.md。

五、把理论落到仓库：如何查看与运行示例

所有代码示例在仓库中按语言分层存放（Python / Java / C++ / C / C# / Go / Swift / Rust / Ruby / Kotlin / TypeScript / Dart / Zig 等），中文版位于 codes/<语言>/chapter_dynamic_programming/，英文版位于 en/codes/<语言>/chapter_dynamic_programming/。每份源码都带 if __name__ == "__main__" 驱动的 Driver Code，直接运行即可看到输出：

# 以 Python 为例，在仓库根目录执行
python3 codes/python/chapter_dynamic_programming/knapsack.py
python3 codes/python/chapter_dynamic_programming/coin_change.py
python3 codes/python/chapter_dynamic_programming/edit_distance.py

仓库还提供了 codes/pythontutor/chapter_dynamic_programming/ 下的可视化走查文档（如 knapsack.md），适合观察 $d p$ 表的逐格填充过程。若要通读本章方法论原文，建议按以下顺序配合阅读：

intro_to_dynamic_programming.md——从回溯到记忆化再到 DP 的演进主线；
dp_problem_features.md——最优子结构与无后效性判定；
knapsack_problem.md、unbounded_knapsack_problem.md、edit_distance_problem.md——三大核心题型的完整推导。

结语

动态规划的章末总结，实际上给出了三条最重要的“可迁移经验”：

遇题先验证三大特征：存在重叠子问题 + 最优子结构 + 无后效性，才谈得上 DP；否则即便写出递推也无法保证正确或高效；
递推方程决定遍历方向：0-1 背包压维后依赖“左上方”必须倒序，完全背包与零钱兑换依赖“正左方”必须正序，而编辑距离同时依赖三个方向则需引入暂存变量兜住左上角——这三类写法覆盖了绝大多数经典 DP 的空间优化套路；
在仓库中“四件套”对照学习：任何一道 DP 题都值得像本仓库源码那样，先写暴力回溯、再补记忆化、再改写迭代填表、最后压缩维度，逐步体会每步改造消除的瓶颈所在。

hello-algo

项目地址：https://gitcode.com/GitHub_Trending/he/hello-algo

登录后查看全文