Hello 算法动态规划全章小结：从重叠子问题到背包与编辑距离的实战要点

《Hello 算法》动态规划章节的日文小结 summary.md 系统回顾了动态规划（Dynamic Programming, DP）的思想内核、三大特性，以及背包问题族与编辑距离问题这两类最重要的应用场景。本文以该小结为骨架，结合仓库中多语言实现源码，逐条展开其中的概念、状态定义、状态转移方程与空间优化技巧，帮助你读完即可对照代码复现每一类问题。

一、动态规划的核心思想：分解、存储与避免重复计算

动态规划的本质可以概括为一句话：把大问题分解为子问题，并存储子问题的解，从而规避重复计算、提高计算效率。总结 summary.md 强调，如果不考虑时间开销，所有动态规划问题都可以用回溯（暴力搜索）求解，但回溯产生的递归树中存在大量重叠子问题，效率极低；而**记忆化（memoization）**通过保存已计算过的子问题解，保证了每个重叠子问题只被计算一次。

从暴力搜索到记忆化搜索

以经典的“爬楼梯”为例，设每步可上 1 阶或 2 阶，问爬上 $n$ 阶的方案数。仓库同时提供了三种实现：

• 暴力回溯 climbing_stairs_backtrack.py：枚举所有走法，复杂度呈指数级；
• 记忆化搜索 climbing_stairs_dfs_mem.py：在递归中查表 mem，命中即返回；
• 递推动态规划 climbing_stairs_dp.py：自底向上填表。

记忆化搜索其实就是带缓存的回溯，这一思路在 0-1 背包（knapsack.py 中的 knapsack_dfs 与 knapsack_dfs_mem）与编辑距离（edit_distance.py 中的 edit_distance_dfs 与 edit_distance_dfs_mem）中同样存在一一对应关系，形成“暴力搜索 → 记忆化搜索 → 动态规划 → 空间优化动态规划”的四级递进，这也是《Hello 算法》各章统一采用的讲解路径。

记忆化搜索（自顶向下）与动态规划（自底向上）

小结中有一个形象的比喻：记忆化搜索是从顶至底的递归式解法；与之对应的动态规划是从底至顶的递推式解法，其过程如同“填写表格”。以爬楼梯的递推实现为例：

# 摘自 climbing_stairs_dp.py
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]

由于当前状态仅依赖若干局部状态（此处为前两个状态），因此可以消除 dp 表的一个维度（一维数组压缩为两个滚动变量），把空间复杂度从 $O(n)$ 降到 $O(1)$，即 climbing_stairs_dp_comp 所做的工作。这类“先二维表、后滚动数组/一维压缩”的模式，贯穿背包问题与编辑距离问题的全部优化，是本小结最重要的实操主线。

二、子问题分解的三种视角与动态规划三大特性

小结指出，子问题分解是一种通用的算法思路，但在分治、动态规划、回溯中具有不同性质：

• 分治算法：将原问题划分为多个相互独立的子问题，回溯时合并各子问题解，子问题之间相互独立；
• 动态规划：同样递归分解，但子问题相互依赖，分解过程中会出现大量重叠子问题，这正是它区别于分治的关键；
• 回溯算法：在尝试与回退中穷举全部候选解，通过剪枝避免无效分支，适合求解“方案/组合”类问题。

在此基础上，可判定的动态规划问题普遍具备三大特性：

1. 重叠子问题：递归树中存在大量被重复求解的子问题；
2. 最优子结构：原问题的最优解可以由子问题的最优解构建而来；
3. 无后效性：给定一个状态，其未来发展只与该状态有关，而与过去经历的所有状态无关。

无后效性为何如此重要

dp_problem_features.md 用“带约束爬楼梯”生动说明了后效性的危害：若规定“不能连续两轮跳 1 阶”，那么下一步选择不能仅由当前所在阶数决定，还与上一轮跳法有关，原状态转移方程 $dp[i] = dp[i-1] + dp[i-2]$ 随即失效。解法是扩展状态定义为 $dp[i, j]$（处于第 $i$ 阶且上一轮跳了 $j$ 阶），借助 climbing_stairs_constraint_dp 的二维状态重新恢复无后效性。

但若问题具有严重的“有后效性”（如某轮落脚会在更高台阶生成障碍、从而影响此后所有跳跃，见 dp_problem_features.md 中的“障碍生成”示例），动态规划往往难以求解。这提醒我们：在动手写状态转移方程之前，先判断问题是否满足无后效性，是选择动态规划算法的重要前置检查。

三、背包问题族：状态定义、转移方程与遍历方向

小结将背包问题称为“最典型的动态规划问题之一”，并逐一给出 0-1 背包、完全背包、零钱兑换与零钱兑换 II 的推导结论，这些内容在中文版文档中对应 knapsack_problem.md 与 unbounded_knapsack_problem.md。

0-1 背包：依赖左上状态，空间优化后必须倒序遍历

0-1 背包中每件物品最多选一次。其状态定义为：前 $i$ 个物品在容量为 $c$ 的背包中所能装下的最大价值。对物品 $i$ 有两种决策——不放入与放入，据此可得状态转移方程：

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

见 knapsack.py 的 knapsack_dp。二维表状态下，每个格子依赖“正上方”与“左上方”两个格子。空间优化为一维数组后，若从左向右遍历，dp[c - w[i-1]] 可能已被本轮覆盖，导致“一件物品被重复选取”，因此必须倒序遍历（knapsack_dp_comp 中 for c in range(cap, 0, -1)），才能保证左上方状态来自上一轮、不被覆盖。

完全背包：依赖正左状态，空间优化后应正序遍历

完全背包中每种物品可选数量不限。由于“选第 $i$ 件”之后仍可继续选它，状态转移方程变为：

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

即“放入”分支从 $dp[i-1,c-w_i]$ 变为 $dp[i,c-w_i]$，依赖正上方与正左方（同一行、更小容量）的状态。正左状态希望被本轮更新覆盖，因此空间优化后应当正序遍历，见 unbounded_knapsack.py 的 unbounded_knapsack_dp_comp。

零钱兑换：从“最大价值”到“最小硬币数”

零钱兑换是完全背包的变种，改动体现在两点（对应 coin_change.py）：

1. 优化目标从求“最大价值”变为求“最小硬币数量”，转移方程中的 $\max()$ 换成 $\min()$：

$$dp[i, a] = \min(dp[i-1, a],\; dp[i, a-c_i] + 1)$$

2. 目标从“不超过背包容量”变为“恰好凑出目标金额”。由于 min 运算需要区分“可行但数量很大”与“完全不可行”，代码用 MAX = amt + 1 表示“无法凑出目标金额”的无效解（比任何可行解数量都大），初始化首行 dp[0][a] = MAX，最终返回时若 dp[n][amt] 仍等于 MAX 则返回 -1。

空间优化版 coin_change_dp_comp 属于完全背包体系，因此同样采用正序遍历。

零钱兑换 II：从“最少数量”到“组合数量”

零钱兑换 II 把求“最少硬币数量”改为求“硬币组合数量”，转移方程相应地把 $\min ()$ 换成求和运算符（见 coin_change_ii.py）：

$$dp[i, a] = dp[i-1, a] + dp[i, a-c_i]$$

边界上，凑出金额 0 只有“一枚都不选”这一种空组合，故首列初始化为 dp[i][0] = 1；由于仍继承完全背包“可重复选取”的结构，空间优化后同样正序遍历。

下表集中对照四类背包变种的关键差异，方便检索记忆：

问题	每件可选次数	目标	转移中的操作	无效解表示	空间优化遍历方向
0-1 背包	≤ 1	价值最大	max，依赖左上	0（默认不可达为 0 价值）	倒序
完全背包	不限	价值最大	max，依赖正左	—	正序
零钱兑换	不限	硬币数最小	min	amt + 1，最终输出 -1	正序
零钱兑换 II	不限	组合数量	求和	首列置 1（空组合）	正序

四、编辑距离问题：三方向依赖与单变量暂存技巧

编辑距离（Levenshtein 距离）用于衡量两个字符串的相似度，定义为从字符串 $s$ 变换到字符串 $t$ 所需的最少编辑步数，允许的编辑操作包括添加、删除、替换。状态定义为：将 $s$ 的前 $i$ 个字符更改为 $t$ 的前 $j$ 个字符所需的最少编辑步数，即 $dp[i, j]$。

状态转移的核心规则（见 edit_distance.py）：

• 当 $s[i-1] = t[j-1]$ 时，当前两个字符相等，无须编辑，直接继承 $dp[i-1, j-1]$；
• 当 $s[i-1] \ne t[j-1]$ 时，存在三种决策，分别对应剩余子问题：
  • 添加：在 $s$ 尾部补一个字符使与 $t[j]$ 对齐，对应 insert = dp[i][j-1]；
  • 删除：删去 $s[i]$，对应 delete = dp[i-1][j]；
  • 替换：把 $s[i]$ 换成 $t[j]$，对应 replace = dp[i-1][j-1]；

取三者最小值再加 1，即

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

边界条件是首行、首列：空串转换为 $j$ 个字符需要 $j$ 次添加，反之需要 $i$ 次删除（源码中 dp[i][0] = i 与 dp[0][j] = j 的初始化）。

为什么编辑距离的空间优化最“麻烦”

编辑距离的状态同时依赖正上方、正左方、左上方三个格子，而一维滚动数组一次只能保留“上一行”的完整信息：

• 若正序遍历，dp[j-1] 已被本轮更新，不再是上一行的值，正左依赖被破坏；
• 若倒序遍历，dp[j] 被覆盖前未保存，左上方依赖同样丢失。

因此小结指出，正序或倒序遍历都无法单独正确完成状态转移。解法是在 edit_distance_dp_comp 中用一个临时变量 leftup 暂存“左上方”状态：每轮先记录 dp[j] 的旧值作为下一列的 leftup，计算 dp[j] 时再取出保存的上轮 leftup。经过这一转换，问题被转化为与完全背包等价的形态，从而可以在空间优化后正序遍历。dp[0] 每轮递增 1，恰好等价于首列的 i（删除 $i$ 个字符的代价），是这段代码里最精巧的边界处理。

五、在本仓库中验证与深入阅读

1. 直接运行验证：上述每个 Python 文件都自带 Driver Code，例如执行 python codes/python/chapter_dynamic_programming/knapsack.py 会依次打印暴力搜索、记忆化搜索、动态规划与空间优化四种实现的输出并互相印证；也可以运行 test_all.py 批量跑完整个 Python 示例集。
2. 跨语言对照：同一套题目在 C（chapter_dynamic_programming）、C++、Java、C#、Go、Swift、Rust、TypeScript 等十余种语言下均有同名实现，可用于对照不同语言在数组滚动与边界初始化上的写法差异。
3. 配套理论文档：动态规划一章的中文正文位于 docs/chapter_dynamic_programming，其中 intro_to_dynamic_programming.md、dp_problem_features.md、dp_solution_pipeline.md 分别对应思想引入、特性判定与“状态定义 → 转移方程 → 边界与优化”的解题流水线；零钱兑换类、背包类与编辑距离的完整推导见同目录下的对应正文文档。

结语：把“小结”当成解题检查清单

回顾整章小结可以发现，它本身就是一张可复用的动态规划解题自检清单：先判断是否具备重叠子问题与最优子结构，再检查无后效性（不满足则考虑扩展状态维度）；随后按“背包类”或“编辑距离类”套用状态定义与转移方程；最后根据依赖方向选择空间优化策略——依赖左上则倒序、依赖正左则正序、同时依赖三方向则引入 leftup 单变量暂存。理解这几条结论背后的“为什么”，比背诵方程本身更能应对新题变形。