Hello 算法动态规划章小结：子问题分解、三大特性与背包/编辑距离源码解析

2026-09-06 14:10:25作者：房伟宁

本文以《Hello 算法》动态规划章节的小结（docs/chapter_dynamic_programming/summary.md）为主体，系统梳理动态规划的核心思想、解题流程、三大特性，并深入解析 0-1 背包、完全背包、零钱兑换与编辑距离四类典型问题。通过结合同章各文档与仓库中 Python 源码实现，帮助你建立"从暴力搜索到空间优化"的完整动态规划心智模型，并掌握可复制、可运行的求解范式。

动态规划的核心思想

动态规划（Dynamic Programming，DP）的本质是对问题进行分解，并通过存储子问题的解来规避重复计算，从而提高计算效率。其关键在于识别出原问题可以被拆解为大量相互依赖的子问题，且这些子问题之间存在重叠——同一子问题会在递归树中被反复求解。

正如小结所概括的：

动态规划对问题进行分解，并通过存储子问题的解来规避重复计算，提高计算效率。
不考虑时间的前提下，所有动态规划问题都可以用回溯（暴力搜索）求解，但递归树中存在大量的重叠子问题，效率极低。通过引入记忆化列表，可以存储所有计算过的子问题的解，从而保证重叠子问题只被计算一次。

也就是说，动态规划并不是凭空出现的算法，而是对暴力回溯搜索结果的重用与优化。理解这一点，是掌握本章所有内容的起点。

三种解法的演进：暴力搜索、记忆化搜索、动态规划

小结指出，记忆化搜索与动态规划分别代表"自顶向下"与"自底向上"两种递推方向：

记忆化搜索是一种从顶至底的递归式解法；
动态规划是一种从底至顶的递推式解法，如同"填写表格"。由于当前状态仅依赖某些局部状态，因此可以消除 $d p$ 表的一个维度，从而降低空间复杂度。

以 0-1 背包为例，仓库源码 knapsack.py 完整展示了这三条技术路线。

方法一：暴力搜索

暴力搜索即回溯穷举，每个物品产生"放入/不放入"两条分支，时间复杂度为 $O (2^{n})$ 。对应 knapsack_dfs 函数：

def knapsack_dfs(wgt: list[int], val: list[int], i: int, c: int) -> int:
    """0-1 背包：暴力搜索"""
    # 若已选完所有物品或背包无剩余容量，则返回价值 0
    if i == 0 or c == 0:
        return 0
    # 若超过背包容量，则只能选择不放入背包
    if wgt[i - 1] > c:
        return knapsack_dfs(wgt, val, i - 1, c)
    # 计算不放入和放入物品 i 的最大价值
    no = knapsack_dfs(wgt, val, i - 1, c)
    yes = knapsack_dfs(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1]
    # 返回两种方案中价值更大的那一个
    return max(no, yes)

其中 i 表示当前物品编号，c 表示背包剩余容量。可以观察到，递归树中存在大量重叠子问题，例如 dp[1, 10] 会被多条路径重复访问。

方法二：记忆化搜索（自顶向下）

引入记忆列表 mem 后，每个子问题只会被真正计算一次，时间复杂度降为 $O(n \times cap)$ 。源码中的 knapsack_dfs_mem 相比暴力搜索只增加了两行逻辑——查询与回写：

def knapsack_dfs_mem(wgt, val, mem, i, c) -> int:
    """0-1 背包：记忆化搜索"""
    if i == 0 or c == 0:
        return 0
    # 若已有记录，则直接返回
    if mem[i][c] != -1:
        return mem[i][c]
    if wgt[i - 1] > c:
        return knapsack_dfs_mem(wgt, val, mem, i - 1, c)
    no = knapsack_dfs_mem(wgt, val, mem, i - 1, c)
    yes = knapsack_dfs_mem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1]
    # 记录并返回
    mem[i][c] = max(no, yes)
    return mem[i][c]

mem 是一个尺寸为 $(n+1) \times (cap+1)$ 的二维数组，以 -1 表示"尚未计算"，这与小结中"记忆化列表存储所有计算过的子问题的解"的描述完全一致。

方法三：动态规划（自底向上）

动态规划将递归改写为迭代，按依赖顺序自底向上填充 $d p$ 表，如同"填写表格"。源码 knapsack_dp 实现如下：

def knapsack_dp(wgt: list[int], val: list[int], cap: int) -> int:
    """0-1 背包：动态规划"""
    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]

这里的双层循环即为"正序遍历整个 $d p$ 表"，时间复杂度与空间复杂度均由数组 dp 大小决定，为 $O(n \times cap)$ 。

空间优化：消除一个维度

小结特别强调"由于当前状态仅依赖某些局部状态，因此我们可以消除 $d p$ 表的一个维度，从而降低空间复杂度"。在 0-1 背包中，每个状态只依赖正上方与左上方的格子，因此可以只保留一行数组，但必须倒序遍历，否则左上方状态会被提前覆盖。源码 knapsack_dp_comp 正是如此：

def knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) -> int:
    """0-1 背包：空间优化后的动态规划"""
    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] = dp[c]
            else:
                dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
    return dp[cap]

for c in range(cap, 0, -1) 的倒序正是小结所述"需要倒序遍历列表，避免左上方状态被覆盖"的源码印证，空间复杂度由 $O(n \times cap)$ 降至 $O (c a p)$ 。

子问题分解的通用性

小结指出：子问题分解是一种通用的算法思路，在分治、动态规划、回溯中具有不同的性质。这一判断在同章文档 dp_problem_features.md 中有明确展开：

分治：递归地将原问题划分为多个相互独立的子问题，直至最小子问题，再在回溯中合并子问题的解。
动态规划：同样对问题递归分解，但子问题相互依赖，分解过程中会出现大量重叠子问题。
回溯：在尝试与回退中穷举所有可能的解，并以剪枝避免不必要的搜索分支。

三者的核心区别在于子问题之间是否重叠、解是否可复用。动态规划正是利用了"子问题重叠"这一性质，将穷举的指数级代价压缩到多项式级。

动态规划的三大特性

小结明确了动态规划问题的三大特性：重叠子问题、最优子结构、无后效性，并对后两者给出了严格定义。

重叠子问题

即递归树中存在大量相同子问题被重复计算，这是引入记忆化 / $d p$ 表的直接动因。在最小路径和（最小路径和见 min_path_sum.py）中，重叠的根源是"存在多条路径可以从左上角到达某一单元格"。

最优子结构

小结定义：如果原问题的最优解可以从子问题的最优解构建得来，则它就具有最优子结构。同章文档用"爬楼梯最小代价"加以说明：

dp[i] = \min(dp[i-1], dp[i-2]) + cost[i]

第 $i$ 阶的最小代价由两个子问题最优解 $d p [i - 1]$ 与 $d p [i - 2]$ 中较优者构建而来。对应源码 min_cost_climbing_stairs_dp.py 中的 min_cost_climbing_stairs_dp。文档同时提示，最优子结构的表述较为灵活：例如"爬楼梯方案数量"看似是计数问题，但改写为"最大方案数量"后，最优子结构即刻浮现—— $d p [n] = d p [n - 1] + d p [n - 2]$ 。

无后效性

小结定义：无后效性指对于一个状态，其未来发展只与该状态有关，而与过去经历的所有状态无关。文档用一个经典反例说明其失效：

带约束爬楼梯（不能连续两轮跳 1 阶）：由于"下一轮选择"依赖于上一轮所在状态， $d p [i] = d p [i - 1] + d p [i - 2]$ 失效。解决之道是扩展状态定义为 $d p [i, j]$ （处在第 $i$ 阶且上一轮跳了 $j$ 阶），重新恢复无后效性，实现见 climbing_stairs_constraint_dp.py。
爬楼梯与障碍生成：每次跳跃都会在未来的更高阶梯上放置障碍，下一步决策依赖过去所有状态，属于"严重有后效性"。对于这类问题，动态规划往往难以解决，文档建议改用启发式搜索、遗传算法、强化学习等，以求在有限时间内得到可用的局部最优解。

这一点很重要：并非所有最优化问题都适合动态规划，许多组合优化问题不具有无后效性，无法使用动态规划快速求解。

背包问题族

小结将背包问题列为本章最典型的动态规划问题，覆盖 0-1 背包、完全背包与多重背包等变种，并逐一给出状态定义与空间优化要点。

0-1 背包

状态定义为前 $i$ 个物品在容量为 $c$ 的背包中的最大价值，记为 $d p [i, c]$ 。
依据"不放入"与"放入"两种决策得到最优子结构，状态转移方程为：

dp[i, c] = \max(dp[i-1, c],\ dp[i-1, c - wgt[i-1]] + val[i-1])

空间优化中，由于每个状态依赖正上方和左上方的状态，需要倒序遍历列表，避免左上方状态被覆盖（见上文 knapsack_dp_comp）。

完全背包

每种物品的选取数量无限制，因此"放入物品"后的转移与 0-1 背包不同：0-1 背包放入物品 $i$ 后只能从前 $i - 1$ 个物品中选，而完全背包放入物品 $i$ 后仍可从当前 $i$ 个物品中选。状态转移方程变为：

dp[i, c] = \max(dp[i-1, c],\ dp[i, c - wgt[i-1]] + val[i-1])

由于状态依赖正上方和正左方的状态，空间优化中应当正序遍历。这恰好与 0-1 背包的倒序相反。实现见 unbounded_knapsack.py 中的 unbounded_knapsack_dp 与 unbounded_knapsack_dp_comp。

零钱兑换问题

小结将零钱兑换视为完全背包的一个变种，并点明两处关键改动：

目标变化：从求"最大"价值变为求"最小"硬币数量，状态转移方程中的 $\max()$ 应改为 $\min()$ 。
约束变化：从追求"不超过"背包容量到追求"恰好"凑出目标金额，因此使用 $a m t + 1$ 来表示"无法凑出目标金额"的无效解。

状态定义为前 $i$ 种硬币能够凑出金额 $a$ 的最少硬币数量 $d p [i, a]$ ，转移方程为：

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

边界处理上，"凑出 $0$ 元"需要 $0$ 枚硬币，故首列 $d p [i, 0] = 0$ ；而多数语言没有真正的 $+ \infty$ ，为避免整型最大值在 +1 时溢出，文档选择用 $a m t + 1$ 表示无效解（因为凑出 $a m t$ 的最多硬币数不超过 $a m t$ ），最终返回前判断是否等于 $a m t + 1$ ，若是则返回 $- 1$ 。实现见 coin_change.py 的 coin_change_dp 与空间优化版 coin_change_dp_comp。

零钱兑换问题 II

小结进一步指出，零钱兑换 II 从求"最少硬币数量"改为求"硬币组合数量"，状态转移方程相应地从 $\min()$ 改为求和运算符：

d p [i, a] = d p [i - 1, a] + d p [i, a - c o i n s [i - 1]]

即当前状态的组合数等于"不选当前硬币"与"选当前硬币"两种决策的组合数之和。注意此处与零钱兑换 I 的一个细微但关键的差别：为枚举"组合"而非"排列"，外层循环必须遍历硬币、内层循环遍历金额，从而保证同一组硬币不会被以不同顺序重复计数。实现见 coin_change_ii.py 的 coin_change_ii_dp 与 coin_change_ii_dp_comp。

编辑距离问题

小结将编辑距离（Levenshtein 距离）定义为从一个字符串到另一个字符串的最少编辑步数，编辑操作包括添加、删除、替换，并给出完整的动态规划建模过程。

状态定义为将 $s$ 的前 $i$ 个字符更改为 $t$ 的前 $j$ 个字符所需的最少编辑步数，记为 $d p [i, j]$ 。
当 $s[i-1] \ne t[j-1]$ $s [i - 1] \neq = t [j - 1]$ 时，具有三种决策——添加、删除、替换，各自对应一个剩余子问题：
- 在 $s [i - 1]$ 后添加 $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]$ 。
当 $s [i - 1] = t [j - 1]$ 时，无须编辑当前字符，直接 $d p [i, j] = d p [i - 1, j - 1]$ 。

据此得到状态转移方程：

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

源码 edit_distance.py 中 edit_distance_dp 的双层循环实现与之逐行对应：

def edit_distance_dp(s: str, t: str) -> int:
    """编辑距离：动态规划"""
    n, m = len(s), len(t)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    # 边界：首行首列
    for i in range(1, n + 1):
        dp[i][0] = i
    for j in range(1, 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] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
    return dp[n][m]

编辑距离的空间优化：暂存左上方状态

小结特别指出编辑距离空间优化的难点：状态依赖正上方、正左方、左上方三个格子，导致"正序遍历会丢失左上方 $d p [i - 1, j - 1]$ ，倒序遍历无法提前构建 $d p [i, j - 1]$ "，因此两种朴素遍历顺序都不可取。解决办法是用一个变量 leftup 暂存左上方的解，从而转化到与完全背包等价的情况，即可正序遍历。源码 edit_distance_dp_comp 完整体现了这一技巧：

def edit_distance_dp_comp(s: str, t: str) -> int:
    """编辑距离：空间优化后的动态规划"""
    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
        for j in range(1, m + 1):
            temp = dp[j]
            if s[i - 1] == t[j - 1]:
                dp[j] = leftup
            else:
                dp[j] = min(dp[j - 1], dp[j], leftup) + 1
            leftup = temp  # 更新为下一轮的 dp[i-1, j-1]
    return dp[m]

这里 temp 保存旧的 $d p [i - 1, j]$ ，leftup 在每轮结束时被更新为"下一列的左上方"，使得单行数组也能正确完成二维的状态转移，空间复杂度降为 $O (m)$ 。

本章要点回顾

结合小结与全章实现，可以提炼出动态规划的完整方法论：

问题分解：将原问题拆解为子问题，识别其是否重叠。
定义状态：状态应包含描述解题进度的所有变量，每个独立变量对应 $d p$ 表的一个维度。
推导转移：找出最优子结构，据此构建状态转移方程。
确定边界与转移顺序：保证在计算某状态时，其依赖的更小子问题已先被正确计算。
空间优化：若当前状态只依赖局部若干状态，可消除一个维度，并依据依赖方向选择正序 / 倒序遍历（0-1 背包倒序、完全背包与编辑距离正序，编辑距离需 leftup 暂存）。
特性检验：以重叠子问题、最优子结构、无后效性为三大判据；不满足无后效性的问题应放弃动态规划，转投启发式或元启发式方法。

本章全部示例代码集中在 codes/python/chapter_dynamic_programming/ 目录下，除上文提及的背包、零钱兑换、编辑距离外，还包括爬楼梯的多种解法（climbing_stairs_backtrack.py、climbing_stairs_dfs.py、climbing_stairs_dfs_mem.py、climbing_stairs_dp.py）与最小路径和（min_path_sum.py），可逐一对比"暴力搜索 → 记忆化搜索 → 动态规划 → 空间优化"四条演进路线，作为动手演练的入口。

hello-algo

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

登录后查看全文