Hello 算法动态规划练习精讲从「能否用 DP」判断到爬楼梯与 0-1 背包一维实现【免费下载链接】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动态规划是《Hello 算法》数据结构与算法教程中最考验「建模能力」的章节之一。本文以仓库俄语版 ru/docs/chapter_dynamic_programming/exercises.md 的练习题为骨架逐一拆解 3 道知识巩固题与 2 道编程题的标准解法并结合 codes/python/chapter_dynamic_programming、codes/go/chapter_dynamic_programming 等目录下的真实源码说明「何时该用动态规划」「如何手算 dp 表的一个格子」「为什么 0-1 背包要倒序遍历容量」等核心问题。读完本文你将掌握判断 DP 适用性的方法论并能独立写出爬楼梯与 0-1 背包的一维动态规划实现。一、知识巩固三问判断 DP 直觉1. 什么时候适合使用动态规划原题场景是一位同学断言「只要能写出递推式就应该使用动态规划」。这个说法并不成立下面三题恰好构成递推式与 DP 适用性的对照组。题目 1使用面值[1, 3, 4]的硬币凑出金额 6求最少硬币数每种硬币可重复使用。适合动态规划。设dp[i]表示凑出金额i所需的最少硬币数。对每枚不超过i的硬币cdp[i-c] 1都是一个候选答案最终取全部候选的最小值。这个问题的关键在于不同选择序列会反复遇到同一个金额例如凑 6 时33与132的中间态都会到达金额 3较大的金额可由较小金额的最优解组合而来——这正是「重叠子问题」与「最优子结构」的体现。金额 6 的答案是 2即3 3。仓库中零钱兑换的 DP 实现见 codes/go/chapter_dynamic_programming/coin_change.go它的状态转移为dp[i][a] min(dp[i-1][a], dp[i][a-coins[i-1]] 1)注意「选硬币」分支读取的是当前行dp[i][a-coins[i-1]]这正是「硬币可重复使用」在转移方程中的体现与不可重复选取的 0-1 背包读取dp[i-1][...]形成鲜明对比。题目 2输出[1, 2, 3]的全部排列。应使用回溯而非动态规划。题目要求逐个生成全部 6 个排列回溯可以系统地「做选择 → 继续搜索 → 撤销选择 → 尝试另一分支」。无论用什么方法实际输出这些排列时都无法跳过枚举而 DP 的价值在于用「记忆」换「重复计算」——当没有重复计算可省时DP 便无从谈起。仓库中爬楼梯的回溯版 codes/go/chapter_dynamic_programming/climbing_stairs_backtrack.go 展示了「选择集 剪枝 尝试/回退」的标准回溯骨架其中choices : []int{1, 2}与statechoice n的剪枝逻辑就是回溯的典型写法。题目 3计算 $1 2 \dots n$。用循环或等差数列求和公式即可。虽然能写出递推式S(i) S(i-1) i但计算S(i)时只依赖一个更小的S(i-1)每个部分和只需计算一次不存在重叠子问题因此建立dp表纯属浪费空间。结论能写递推式 ≠ 需要动态规划。DP 的适用前提是「重叠子问题 最优子结构」相关系统论述可参阅 ru/docs/chapter_dynamic_programming/dp_problem_features.md。2. 背包表中的一个格子怎么算给定 0-1 背包实例物品重量wgt [1, 2, 3]价值val [5, 11, 15]背包容量 4。dp[i][c]表示只考虑前i件物品、容量上限为c时的最大价值不要求恰好装满。已知dp[2][4] 16、dp[2][1] 5手算dp[3][4]不选第 3 件物品沿用前两件物品的结果候选价值为dp[2][4] 16选第 3 件物品第 3 件物品重量为 3放入后剩容量 $4-31$候选价值为dp[2][1] 15 5 15 20取最大值比较 16 与 20dp[3][4] 20对应选择第 1、3 件物品总重量 $134$总价值 $51520$。这一格的计算完整演示了 0-1 背包的「选 / 不选」二元决策。对应的二维 DP 实现见 codes/python/chapter_dynamic_programming/knapsack.py 与 codes/c/chapter_dynamic_programming/knapsack.c其转移方程为dp[i][c] max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] val[i - 1])注意两个分支读取的都是i - 1行即「当前物品至多被选一次」。完整理论推导见 ru/docs/chapter_dynamic_programming/knapsack_problem.md。3. 背包容量应该按什么顺序更新设 0-1 背包只有一件物品重量 2、价值 5容量 4初始一维数组dp [0, 0, 0, 0, 0]。若按容量从小到大2 → 4更新更新dp[2]得 5更新dp[3]得 5更新dp[4]时读取刚更新的dp[2]得到dp[4] 5 5 10。答案dp[4] 10是错误的——价值 10 等价于把这件物品放入了两次违反「每件物品最多选择一次」正确值应为dp[4] 5处理每件物品时应从大到小更新容量依次 4、3、2这样计算dp[c]时读到的dp[c-2]仍是「上一轮未处理当前物品」的结果从而避免同一轮内重复使用当前物品。仓库一维版本完美印证了这一顺序Python 实现 codes/python/chapter_dynamic_programming/knapsack.py 使用for c in range(cap, 0, -1)倒序遍历C 语言版 codes/c/chapter_dynamic_programming/knapsack.c 同样使用for (int c cap; c 1; c--)。「0-1 背包倒序、完全背包正序」这条一维优化的铁律正是源于这里防止物品被重复选择的考虑正序遍历的场景可对照零钱兑换实现 codes/go/chapter_dynamic_programming/coin_change.go 以及 ru/docs/chapter_dynamic_programming/unbounded_knapsack_problem.md。二、编程练习两道经典 DP 上手题4. 爬楼梯的方案数一段楼梯共n阶n 1每次只能走 1 阶或 2 阶必须恰好到达第n阶求不同走法总数只按步幅序列区分。题目要求用一维 dp 数组暂不做只保留两个状态的滚动变量优化。解题提示给出完整推导链到达第i阶的最后一步只可能跨 1 阶或 2 阶因此dp[i] dp[i-1] dp[i-2]先处理n为 1、2 的初始情况再从第 3 阶开始填表。仓库参考实现见 codes/python/chapter_dynamic_programming/climbing_stairs_dp.pydef climbing_stairs_dp(n: int) - int: if n 1 or n 2: return n dp [0] * (n 1) # 初始化 dp 表 dp[1], dp[2] 1, 2 # 初始状态 for i in range(3, n 1): # 状态转移 dp[i] dp[i - 1] dp[i - 2] return dp[n]Java 版见 codes/java/chapter_dynamic_programming/climbing_stairs_dp.java逻辑完全一致。题目还提示参考题解虽然常给出滚动变量压缩空间的写法如dp_comp只用两个变量a, b但本练习要求先实现完整的一维 dp 表滚动变量仅作为选做优化这有助于你先看清「状态定义 → 初始状态 → 转移方程」的完整脉络。5. 0-1 背包一维动态规划给定等长数组wgt与val第i件物品重量为正整数wgt[i]、价值为非负整数val[i]背包容量cap为非负整数每件物品最多选一次求总重量不超过cap时的最大总价值要求用一维 DP 实现。解题提示给出的三步初始化长度为cap 1的数组dpdp[c]表示容量上限为c时的最大价值处理物品i时比较「不选它」的dp[c]与「选它」的dp[c-wgt[i]] val[i]容量必须从大到小更新避免同一轮中重复选择当前物品。这正是「知识巩固」第 3 题结论的直接落地。参考实现见 codes/python/chapter_dynamic_programming/knapsack.pydef knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) - int: n len(wgt) dp [0] * (cap 1) # 一维 dp 表 for i in range(1, n 1): for c in range(cap, 0, -1): # 倒序遍历容量 if wgt[i - 1] c: # 放不下只能不选 dp[c] dp[c] else: # 不选 vs 选取较大值 dp[c] max(dp[c], dp[c - wgt[i - 1]] val[i - 1]) return dp[cap]该文件同时提供了暴力搜索knapsack_dfs、记忆化搜索knapsack_dfs_mem、二维 DPknapsack_dp三个对照版本建议按「暴力 → 记忆化 → 二维 DP → 一维 DP」的顺序递进阅读体会重叠子问题如何被逐步消除、空间如何被逐步压缩。如需回溯、搜索等其他思路的整体回顾可参见 ru/docs/chapter_dynamic_programming/intro_to_dynamic_programming.md 与 ru/docs/chapter_dynamic_programming/dp_solution_pipeline.md。三、小结练习题背后的四条 DP 心法综合上述 5 道题可以提炼出四条可复用的判断准则准则对应题目关键判断有重叠子问题才谈 DP零钱兑换 vs 等差数列求和同一子问题是否被反复求解最优子结构支撑转移0-1 背包dp[3][4]大问题最优解能否由子问题最优解构成转移方程决定遍历顺序容量更新顺序读取的是「本轮」还是「上轮」状态决定正序/倒序状态设计决定空间开销爬楼梯 / 0-1 背包一维化仅依赖相邻状态时可压缩 dp 表练习题的完整原文含参考答案与提示见 ru/docs/chapter_dynamic_programming/exercises.md中文对照版见 docs/chapter_dynamic_programming/exercises.md。动笔前建议先独立完成这 5 道题再对照仓库源码验证手算一遍dp[3][4]、手推一遍「倒序更新」比读十遍公式都更有效。【免费下载链接】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），仅供参考