Hello 算法动态规划章小结：重叠子问题、最优子结构与状态转移方程的系统回顾

Hello 算法动态规划章小结：重叠子问题、最优子结构与状态转移方程的系统回顾

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

动态规划（Dynamic Programming）是《Hello 算法》数据结构与算法体系中最重要的解题范式之一：它将原问题分解为一系列相互依赖的子问题，并通过存储子问题的解来规避重复计算，从而大幅提升求解效率。本章小结基于 zh-hant/docs/chapter_dynamic_programming/summary.md 的核心脉络，完整梳理动态规划的三大特性、从暴力搜索到记忆化搜索再到动态规划的演进路径、0-1 背包与完全背包家族（含零钱兑换两兄弟）以及编辑距离问题的状态定义、状态转移方程与空间优化技巧，并结合仓库中的 Python 源码逐行印证，帮助读者建立一张可随时查阅的“动态规划知识地图”。

一、动态规划的核心思想：分解 + 存储，杜绝重复计算

动态规划的基本思路只有两句话：对问题进行分解，并通过存储子问题的解来规避重复计算。以章节开篇的“爬楼梯”问题为例（intro_to_dynamic_programming.md），爬到第 $i$ 阶只能从第 $i-1$ 阶或第 $i-2$ 阶迈上来，因此方案数满足递推关系：

$$ dp[i] = dp[i-1] + dp[i-2] $$

其中 $dp[i]$ 表示爬到第 $i$ 阶的方案数，$dp[1] = 1$、$dp[2] = 2$ 为已知的初始状态。如果不加任何优化直接递归求解，递归树中存在大量重叠子问题（例如 $dp[7]$ 同时出现在 $dp[9]$ 与 $dp[8]$ 的分支中），时间复杂度高达 $O(2^n)$。为解决这一问题，章节给出了经典的三步演进路线。

1.1 从暴力搜索到记忆化搜索：只算一次重叠子问题

暴力搜索以 $dp[n]$ 为起点不断向下递归分解，代码虽简洁但存在指数级冗余（climbing_stairs_dfs.py）。记忆化搜索则声明一个数组mem记录每个子问题的解：首次计算 $dp[i]$ 时存入mem[i]，后续再次需要时直接读取，从而保证所有重叠子问题只被计算一次，时间复杂度从 $O(2^n)$ 骤降至 $O(n)$（climbing_stairs_dfs_mem.py）。

1.2 从记忆化搜索到动态规划：从顶至底 vs 从底至顶

• 记忆化搜索是从顶至底的递归式解法：从原问题（根节点）出发，递归分解到最小子问题（叶节点），再回溯逐层组装答案；
• 动态规划是从底至顶的递推式解法：从最小子问题的解出发，用循环迭代逐层构建更大的子问题，如同“填写表格”一般（climbing_stairs_dp.py）。

由此引出动态规划的三大术语：

1.3 空间优化：滚动变量与降维

由于 $dp[i]$ 只依赖 $dp[i-1]$ 与 $dp[i-2]$，无须保留整个 dp 表，只需两个变量滚动前进，即可将空间复杂度从 $O(n)$ 降至 $O(1)$（climbing_stairs_dp.py 中的climbing_stairs_dp_comp）。这种“当前状态仅依赖有限个局部状态 → 消除 dp 表一个维度”的技巧，被统称为滚动变量（滚动数组），是贯穿本章所有例题的通用优化手段。

二、动态规划问题的三大特性

并非所有可分解的问题都适合动态规划。一个合格的 DP 问题通常同时具备三大特性（dp_problem_features.md）：

2.1 重叠子问题

在分解过程中，同一个子问题会被多次求解。这是“为什么需要 dp 表/记忆数组”的根本原因，也是动态规划相比分治算法最本质的区别——分治的子问题相互独立，而 DP 的子问题相互依赖、彼此重叠。

2.2 最优子结构

如果原问题的最优解可以由子问题的最优解构建得来，则问题具有最优子结构。章节用“爬楼梯最小代价”问题加以说明（min_cost_climbing_stairs_dp.py）：设 $dp[i]$ 为爬到第 $i$ 阶的累计最小代价，则

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

即从两个子问题最优解中挑选较优者构造原问题最优解。值得注意的是，最优子结构的解读方式相当灵活：爬楼梯原题看似是计数问题，但若改问“最大方案数量”，等价命题下最优子结构同样浮现——第 $n$ 阶最大方案数量等于前两阶最大方案数量之和。

2.3 无后效性

无后效性指对于一个确定的状态，其未来发展只与该状态有关，而与过去经历的所有状态无关。以爬楼梯为例，给定状态 $i$，无论此前如何走到第 $i$ 阶，之后都只会发展出 $i+1$ 与 $i+2$ 两个状态，历史不影响未来。

一旦加入约束，无后效性就可能被破坏。章节给出了两个典型反例：

• 带约束爬楼梯：规定“不能连续两轮跳 1 阶”后，下一步选择不能仅由当前阶数决定，还依赖上一轮的选择。解法是扩展状态定义，用 $[i, j]$ 表示“处在第 $i$ 阶且上一轮跳了 $j$ 阶”，通过状态拆分重新恢复无后效性（climbing_stairs_constraint_dp.py）；
• 爬楼梯与障碍生成：规定“爬到第 $i$ 阶时系统会在第 $2i$ 阶放置障碍”，此时每次跳跃都依赖过去所有状态，动态规划难以求解。

许多组合优化问题（如旅行商问题）不具有无后效性，无法用动态规划快速求解，通常需要转向启发式搜索、遗传算法、强化学习等近似方法。这提醒我们：判断一个优化问题能否使用 DP，无后效性是硬门槛。

三、子问题分解：分治、动态规划、回溯的三种视角

子问题分解是一种通用的算法思想，但在三大算法范式中的性质截然不同（dp_problem_features.md）：

在dp_solution_pipeline.md中，章节进一步给出了实用的问题判断方法：先观察问题是否满足“决策树模型”（有明确决策、解由一系列决策产生）；若具备“最大/最小”“最多/最少”等优化描述、状态可用列表/矩阵/树表示且存在递推关系，则为加分项；若目标是找出所有方案、有明显排列组合特征，则为减分项。同时总结了标准解题五步：描述决策 → 定义状态 → 建立 dp 表 → 推导状态转移方程 → 确定边界条件与转移顺序，并以“最小路径和”问题（min_path_sum.py）完整演示了“暴力搜索 → 记忆化搜索 → 动态规划 → 空间优化”的全过程。

四、背包问题家族：从 0-1 背包到零钱兑换

背包问题是动态规划最典型的问题形式，具有 0-1 背包、完全背包、多重背包等变种。本章的核心是通过对比 0-1 背包与完全背包的转移方程差异，理解遍历顺序与空间优化的本质。

4.1 0-1 背包：倒序遍历的经典

问题定义：给定 $n$ 个物品，第 $i$ 个物品重量为 $wgt[i-1]$、价值为 $val[i-1]$，背包容量为 $cap$，每个物品只能选一次，求最大价值（knapsack_problem.md）。

状态定义：$dp[i, c]$ 表示前 $i$ 个物品在容量为 $c$ 的背包中的最大价值，dp 表尺寸为 $(n+1) \times (cap+1)$。

状态转移方程（核心是“不放入 / 放入”两种决策）：

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

空间优化关键：每个状态依赖正上方 $dp[i-1, c]$ 与左上方 $dp[i-1, c-wgt[i-1]]$。只保留一维数组时，若正序遍历，左上方状态会被提前覆盖；因此内层循环必须倒序遍历（knapsack.py 中的knapsack_dp_comp），将空间复杂度从 $O(n \times cap)$ 降至 $O(cap)$：

def knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) -> int: 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]

4.2 完全背包：物品无限次选取，正序遍历

完全背包与 0-1 背包的唯一区别是每种物品可以重复选取（unbounded_knapsack_problem.md）。因此放入物品 $i$ 后，剩余子问题不再是前 $i-1$ 个物品，而是仍包含物品 $i$ 的前 $i$ 个物品，状态转移到 $[i, c - wgt[i-1]]$：

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

对比 0-1 背包，代码只有一处从 $i-1$ 变为 $i$。由于状态依赖正上方与正左方，空间优化后应当正序遍历每一行，与 0-1 背包正好相反（unbounded_knapsack.py）。

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

零钱兑换是完全背包问题的变种（coin_change.py）：目标从求最大价值变为求最少硬币数量，约束从“不超过背包容量”变为“恰好凑出目标金额”。其状态转移方程与完全背包存在两点差异：

1. 优化方向相反，$\max()$ 改为 $\min()$；
2. 优化主体是硬币数量，选中硬币时执行 $+1$：

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

无效解的表示是本体的实现要点：无硬币时无法凑出任意大于 0 的金额，理论上是 $+\infty$，但编程语言中int最大值做 $+1$ 运算可能溢出。由于凑出金额 $amt$ 最多需要 $amt$ 枚硬币，代码采用$amt + 1$ 表示无效解，最后检查 $dp[n, amt]$ 是否等于 $amt + 1$，是则返回 $-1$ 表示无法凑出（见 coin_change.py 的coin_change_dp）。边界条件为：首列 $dp[i, 0] = 0$（金额为 0 时无需硬币），首行 $dp[0, a] = amt + 1$（无硬币时无效）。

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

零钱兑换 II 将目标从求最少硬币数量改为求凑出目标金额的硬币组合数量（coin_change_ii.py），状态转移方程相应地从 $\min()$ 变为求和：

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

边界条件随之变化：首列 $dp[i, 0] = 1$（金额为 0 时有一种组合——不选任何硬币），首行 $dp[0, a] = 0$（无硬币时无法凑出正金额）。空间优化同样删除硬币维度并正序遍历。

4.5 背包家族遍历顺序对照表

记忆口诀：能否重复选取决定了正序还是倒序——物品不可重复（0-1 背包）必须倒序防止覆盖；物品可重复（完全背包及变种）则正序允许累加。

五、编辑距离问题：Levenshtein 距离与 leftup 技巧

5.1 问题定义与状态

编辑距离（Levenshtein 距离）用于衡量两个字符串的相似度，定义为将一个字符串转换为另一个字符串所需的最少编辑步数，允许的编辑操作包括插入、删除、替换（edit_distance_problem.md）。例如将kitten转换为sitting需要 3 步（2 次替换 + 1 次新增）。该问题天然满足决策树模型，目标是求两个节点间的最短路径。

状态定义：$dp[i, j]$ 表示将 $s$ 的前 $i$ 个字符更改为 $t$ 的前 $j$ 个字符所需的最少编辑步数，dp 表尺寸为 $(n+1) \times (m+1)$。

5.2 状态转移方程

当尾部字符 $s[i-1] \ne t[j-1]$ 时，有三种决策，各自对应一个剩余子问题：

• 插入$t[j-1]$：剩余子问题 $dp[i, j-1]$；
• 删除$s[i-1]$：剩余子问题 $dp[i-1, j]$；
• 替换$s[i-1]$ 为 $t[j-1]$：剩余子问题 $dp[i-1, j-1]$。

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

而当 $s[i-1] = t[j-1]$ 时无须编辑当前字符，直接继承左上角：

$$ dp[i, j] = dp[i-1, j-1] $$

边界条件：$dp[0, 0] = 0$（双空串），首行 $dp[0, j] = j$（s 为空则需插入 j 次），首列 $dp[i, 0] = i$（t 为空则需删除 i 次）。

5.3 空间优化：用变量暂存左上角

编辑距离的状态同时依赖正上方、正左方、左上方三个状态，因此空间优化后无论正序还是倒序遍历都无法正确转移：正序遍历丢失左上角 $dp[i-1, j-1]$，倒序遍历又无法提前构建 $dp[i, j-1]$。解法是引入一个变量leftup暂存左上角状态，从而转化为与完全背包等价的情形，可以正序遍历（edit_distance.py 中的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]

leftup在每轮开始时保存上一行对应位置的值，并在内层循环中滚动更新，恰好补齐了被一维数组“挤掉”的左上方维度。

六、小结：一图读懂本章的知识结构

本章的动态规划知识体系可归纳为一条主线与两个分支：

• 一条主线：暴力搜索（$O(2^n)$）→ 记忆化搜索（存储子问题解）→ 动态规划（自底向上填表）→ 空间优化（滚动数组降维），以爬楼梯问题（intro_to_dynamic_programming.md）为完整示范；
• 分支一：背包家族，由 0-1 背包（倒序遍历）扩展到完全背包（正序遍历），再到零钱兑换（$\min$ + $amt+1$ 无效解）与零钱兑换 II（求和计数）；
• 分支二：编辑距离，在三维依赖下用leftup变量实现空间优化，与完全背包在转移结构上等价。

所有例题均遵循统一的“三步走”方法论：定义状态 → 推导状态转移方程 → 确定边界条件与转移顺序（dp_solution_pipeline.md）。实践中判断一个优化问题能否用 DP 求解，只需依次核对三大特性——重叠子问题、最优子结构、无后效性，三者齐备即可放心建表递推。

延伸阅读与源码：完整推导见 knapsack_problem.md、unbounded_knapsack_problem.md、edit_distance_problem.md 与 dp_problem_features.md；所有解法均可在仓库中一键运行的 Python 源码中找到对应实现（knapsack.py、unbounded_knapsack.py、coin_change.py、coin_change_ii.py、edit_distance.py），读者可运行各文件的 Driver Code 观察输出，与文中方程逐一对照验证。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo