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。由此引出动态规划的三大术语术语含义爬楼梯示例dp 表存储所有子问题解的数组$dp[i]$ 表示状态 $i$ 对应子问题的解数组dp初始状态最小子问题对应的状态解已知$dp[1]1$、$dp[2]2$状态转移方程描述子问题之间递推关系的公式$dp[i] dp[i-1] dp[i-2]$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.md2.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$ 阶之后都只会发展出 $i1$ 与 $i2$ 两个状态历史不影响未来。一旦加入约束无后效性就可能被破坏。章节给出了两个典型反例带约束爬楼梯规定“不能连续两轮跳 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 表尺寸为 $(n1) \times (cap1)$。状态转移方程核心是“不放入 / 放入”两种决策$$ 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目标从求最大价值变为求最少硬币数量约束从“不超过背包容量”变为“恰好凑出目标金额”。其状态转移方程与完全背包存在两点差异优化方向相反$\max()$ 改为 $\min()$优化主体是硬币数量选中硬币时执行 $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 背包价值最大正上方 左上方倒序无完全背包价值最大正上方 正左方正序无零钱兑换硬币最少正上方 正左方正序$amt 1$返回前判等输出 $-1$零钱兑换 II组合数量正上方 正左方正序无记忆口诀能否重复选取决定了正序还是倒序——物品不可重复0-1 背包必须倒序防止覆盖物品可重复完全背包及变种则正序允许累加。五、编辑距离问题Levenshtein 距离与 leftup 技巧5.1 问题定义与状态编辑距离Levenshtein 距离用于衡量两个字符串的相似度定义为将一个字符串转换为另一个字符串所需的最少编辑步数允许的编辑操作包括插入、删除、替换edit_distance_problem.md。例如将kitten转换为sitting需要 3 步2 次替换 1 次新增。该问题天然满足决策树模型目标是求两个节点间的最短路径。状态定义$dp[i, j]$ 表示将 $s$ 的前 $i$ 个字符更改为 $t$ 的前 $j$ 个字符所需的最少编辑步数dp 表尺寸为 $(n1) \times (m1)$。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_compdef 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$ $amt1$ 无效解与零钱兑换 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考