Hello 算法动态规划习题精讲：DP 适用性判据、0-1 背包状态推导与遍历顺序实战

导读

本篇文章围绕《Hello 算法》英文版动态规划章节的课后练习与解析展开，系统拆解动态规划（DP）题目中最高频的三类难点：如何判断一道题该用 DP 还是回溯或纯数学公式、如何在 0-1 背包的状态表中手算单个格子、为什么一维滚动数组必须按容量从大到小更新，并以两道编程题为实战落点给出可直接运行的参考实现。读完本文，你将具备用「重叠子问题 + 最优子结构」双重判据做题型决策、徒手推演 dp 状态转移，以及写出正确空间优化代码的能力。

需要说明的是，这些题目位于动态规划章节末尾，用于检验正文章节的知识点：爬楼梯题的完整推导见「动态规划初探」，0-1 背包的两维状态表与空间优化见「0-1 背包问题」，DP 的两大特征（最优子结构、无后效性）则归纳于「动态规划问题特性」。

概念复习一：什么情况下才适合用动态规划？

题目给出学生的论断——「只要一个递推关系能被写出来，就应该用动态规划」——要求对下面三个任务分别判断应使用 DP、回溯，还是无需 dp 表的循环或数学公式，并给出一个核心理由。

任务 1：面值 [1, 3, 4]，凑出金额 6 且硬币数最少（每种面值可重复使用）

结论：适合动态规划。

设 dp[i] 表示凑出金额 i 所需的最少硬币数。对每个不超过 i 的硬币面值 c，dp[i-c] + 1 都是一个候选解，取全部候选中的最小值即可：

dp[i] = min(dp[i-1], dp[i-3], dp[i-4]) + 1   （当对应面值不超过 i 时）

该问题有两个关键结构特征，使得 DP 成为最优解：

• 最优子结构：凑出大金额的最优解可以由凑出更小金额的最优解拼装而成；
• 重叠子问题：不同的「凑法路径」会反复经过相同的金额状态（例如凑 6 时会反复需要凑 3、凑 2 的结果）。

因此手推结果：凑 6 只需 2 枚硬币，方案是 3 + 3。仓库中 coin_change.py 的 coin_change_dp 实现了完全背包形式的二维 DP，其状态转移取 min 且允许重复使用当前硬币（dp[i][a - coins[i-1]] + 1），与本题的「可重复使用」设定一一对应。

任务 2：输出 [1, 2, 3] 的全排列

结论：适合回溯（Backtracking）。

全排列问题的求解目标是逐一枚举并输出全部 $3!=6$ 种排列。回溯正是「做选择 → 继续搜索 → 撤销选择 → 换分支」的系统化枚举器；即便使用 DP，最终依然要逐个输出所有排列，枚举总量不会减少。也就是说，本题没有需要复用的重叠子结果，收益点在「穷举所有路径」而非「缓存中间解」。仓库回溯章节的 permutations_i 系列即是这类枚举型题目的直接样例。

任务 3：计算 $1 + 2 + \dots + n$

结论：循环或等差求和公式即可，不需要 DP。

虽然递推式 $S(i) = S(i-1) + i$ 显然成立，但计算 $S(i)$ 只依赖唯一前驱 $S(i-1)$，每个前缀和只需算一次，没有重叠子问题，也就不需要 dp 表来「去重」或「复用」。

这一问点出了全文最重要的认知：「能写出递推关系」是 DP 的必要不充分条件。DP 的适用门槛是递推过程中存在被重复求解的相同子状态。若缺少重叠子问题，递推退化为普通迭代；若只求最优值而无需列举路径、且子问题高度重叠，DP 才真正发挥指数级加速作用。在正文中，爬楼梯与 0-1 背包正是先通过回溯树观察到重叠子问题（见 intro_to_dynamic_programming.md 对 $O(2^n)$ 递归树的分析），才逐步过渡到 DP。

概念复习二：徒手计算 0-1 背包状态表的单个格子 dp[3][4]

题目给定 0-1 背包数据：重量 wgt = [1, 2, 3]，价值 val = [5, 11, 15]，容量上限 cap = 4。定义 dp[i][c] 为「仅用前 i 个物品、容量上限 c 时能获得的最大价值」（不要求恰好装满），已知 dp[2][4] = 16、dp[2][1] = 5，要求只算 dp[3][4]。

逐步推演「选 / 不选」第三件物品

第三件物品重量 3、价值 15，它面临两种互斥决策：

1. 不选第三件：直接继承前两件的结果，候选值为 dp[2][4] = 16；
2. 选第三件：消耗容量 3，剩余容量 $4 - 3 = 1$，价值增加 15，候选值为 dp[2][1] + 15 = 5 + 15 = 20；
3. 取较大者：dp[3][4] = max(16, 20) = 20。对应选择方案为第 1 件与第 3 件：总重量 $1 + 3 = 4$，总价值 $5 + 15 = 20$，恰好填满容量。

这个单格运算演示的正是 0-1 背包的状态转移方程：

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

其完整推导（含容量不足 wgt[i-1] > c 时只能不选的分支）记录在「0-1 背包问题」正文中。作为延伸验证，读者可以按「先逐物品、再逐容量」的顺序把整张表填完：

dp[i][c]	c=0	c=1	c=2	c=3	c=4
i=0（无物品）	0	0	0	0	0
i=1（w=1,v=5）	0	5	5	5	5
i=2（w=2,v=11）	0	5	11	16	16
i=3（w=3,v=15）	0	5	11	16	20

表中 dp[2][4] = 16、dp[2][1] = 5 与题目给定值完全吻合，最终 dp[3][4] = 20 亦与答案一致，可作为自测基准。二维实现的完整代码见 knapsack.py 的 knapsack_dp 函数，其时间复杂度与空间复杂度均为 $O(n \times cap)$。

概念复习三：一维滚动数组为什么必须「容量从大到小」更新？

这是 0-1 背包中最容易写错的细节。题目设定只有一件物品（重量 2、价值 5），容量上限 4，每件最多选一次，初始一维数组 dp = [0, 0, 0, 0, 0]。

错误示范：从小到大更新会「把物品放两次」

若学生按容量 2 → 3 → 4 的顺序更新：

• 更新 dp[2] 后值为 5；
• 更新 dp[3] 后值为 5（剩余容量 $3-2=1$，无法再放入同一物品）；
• 但当更新 dp[4] 时，读到的是本轮刚写入的新值 dp[2] = 5，于是算出 dp[4] = dp[2] + 5 = 10。

10 等价于把价值 5 的物品放进背包两次，违反「每件物品最多选一次」的约束，因此答案是错误的。由于只有一件物品，正确结果应为 dp[4] = 5。

正确写法：按 4、3、2 的顺序逆序更新

容量应当从大到小更新。这样在计算 dp[c] 时，所读取的 dp[c - wgt[i-1]] 仍然是处理当前物品之前（即上一轮 i-1 行）的值，从根本上杜绝了当前物品在同轮内被重复使用。

处理单个物品（重量 w、价值 v）时：
for c in range(cap, w - 1, -1):   # 逆序：cap → w
    dp[c] = max(dp[c], dp[c - w] + v)

正文「0-1 背包的空间优化」一节给出了更深刻的解释：每个状态只依赖正上方与左上方的格子；若只有一行数组且正向遍历，左上方的旧值 dp[i-1][1..j-1] 会被新值覆盖，从而污染状态转移；逆序遍历则不存在覆盖问题。

与之形成鲜明对照的是完全背包（如硬币找零，每件可无限次使用）：空间优化版本反而要从小到大正向遍历，正是为了让 dp[c - coin] 可以读到本轮刚更新的值、从而实现「重复使用当前硬币」。这一点在仓库 coin_change.py 的 coin_change_dp_comp 中可见一斑——其内层循环注释明确写着 # Traverse in forward order（正向遍历），与该题答案要求恰好相反。遍历方向本身就是「每种物品能否重复使用」这一约束的直接编码，也是阅读他人 DP 代码时最值得先看的判别线索。

编程练习一：爬楼梯方案数（一维 DP）

题目：楼梯共 n 阶，每次只能走 1 或 2 阶且必须恰好落在第 n 阶，统计到达顶层的方法总数。约定 n >= 1，不同方案按「1 阶与 2 阶移动的序列」区分。要求使用一维 dp 数组，暂不采用只保留两个状态的滚动优化。

思路要点

• 最后一步视角：到达第 i 阶的最后一步只能是从第 i-1 阶迈 1 阶，或从第 i-2 阶迈 2 阶；
• 因此状态转移为 dp[i] = dp[i-1] + dp[i-2]，这正是正文中推导出的爬楼梯递推关系；
• 边界初值：dp[1] = 1、dp[2] = 2，从 i = 3 开始逐阶填充。

参考实现（源自仓库源码）

仓库 climbing_stairs_dp.py 的 climbing_stairs_dp 给出了一维数组的完整解法：

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]

复杂度与延伸

该实现时间与空间复杂度均为 $O(n)$。若进一步做滚动压缩，只需保留 a, b 两个变量循环更新（同一文件中的 climbing_stairs_dp_comp），空间可降至 $O(1)$——这恰是题目中「暂不使用」的优化，作为完成后对比练习非常合适。若想回看 DP 是如何从回溯暴力解一步步演化而来，可对照同目录下的 climbing_stairs_backtrack.py、climbing_stairs_dfs.py 与 climbing_stairs_dfs_mem.py。本题即 LeetCode 经典题 Climbing Stairs 的等价表述。

编程练习二：0-1 背包的一维 DP 实现

题目：给定等长数组 wgt 与 val，物品 i 有正整数重量 wgt[i] 与非负整数值 val[i]，背包容量 cap 为非负整数，每件物品最多选一次，求不超容量前提下的最大总价值，要求使用一维 DP。

思路要点

• 初始化长度 cap + 1 的数组 dp，dp[c] 表示容量上限 c 下的最大价值，初值全 0；
• 逐个处理物品 i：dp[c] 代表「不选」，dp[c - wgt[i-1]] + val[i-1] 代表「选」，两者取 max；
• 关键约束：容量从大到小更新，避免同轮内重复选取当前物品（原因即概念复习三的分析）。

参考实现（源自仓库源码）

仓库 knapsack.py 的 knapsack_dp_comp 正是标准一维写法：

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]

同一文件中还提供了三个递进版本供对照学习：暴力搜索 knapsack_dfs（$O(2^n)$）、记忆化搜索 knapsack_dfs_mem（$O(n \times cap)$）与二维表 DP knapsack_dp。习题把实现约束在「一维 DP」上，正是为了让读者亲自体会从二维表删除 i 维度、并将内层循环改为逆序这一系列改动的必要性。

自测数据与验证

可借助 knapsack.py 驱动代码段中的数据集做端到端验证：wgt = [10, 20, 30, 40, 50]、val = [50, 120, 150, 210, 240]、cap = 50，四种方法应输出一致的最大价值结果。若手写版本输出与仓库实现不一致，优先检查「容量是否逆序」以及 wgt[i-1] > c 的越界分支是否处理完整。

从习题到源码：仓库中的跨语言对照

上述每道题在仓库各主流语言的动态规划目录下都有同构实现，方便读者对照语法差异。以 Python 为基准，其余语言对应文件通常位于 en/codes/<语言>/chapter_dynamic_programming/ 下：

• 爬楼梯：climbing_stairs_dp / climbing_stairs_dp_comp（一维 DP 与滚动压缩）；
• 0-1 背包：knapsack（含 dfs、dfs_mem、dp、dp_comp 四个递进解法）；
• 硬币找零（完全背包对照）：coin_change（coin_change_dp_comp 采用正向遍历，与 0-1 背包的逆序形成约束对比）。

运行 Python 示例可执行对应文件（如 python en/codes/python/chapter_dynamic_programming/knapsack.py），其 if __name__ == "__main__" 驱动代码会打印四种解法的一致性结果。建议按「暴力搜索 → 记忆化 → 二维 DP → 一维滚动 DP」的递进顺序阅读同文件内的多个函数，这会帮助你建立从回溯树观察到重叠子问题、再到空间优化的完整心法。

小结

动态规划题的成败往往不在「写出递推式」，而在正确的题型判断与正确的遍历设计：先以重叠子问题与最优子结构确认 DP 的适用性，再厘清每件物品是否可重复使用（决定容量遍历方向），最后用滚动数组压缩空间。把本文两题三问吃透，配合仓库中的多解法源码与本章小结文档中的概念清单，即可为后续的完全背包、编辑距离、路径计数等进阶题型打下坚实基础。