第 106 节 · SECTION 106
练习
知识巩固
什么时候适合使用动态规划
一位同学说：“只要能写出递推式，就应该使用动态规划。”
请判断下面三个任务分别更适合使用动态规划、回溯，还是使用循环或数学公式而不建立 dp 表，并写出一个关键理由。
-
使用面值
[1, 3, 4]的硬币凑出金额 6，求最少硬币数，每种硬币可重复使用； -
输出
[1, 2, 3]的全部排列； -
计算 $1 + 2 + \dots + n$。
对于你判断为适合动态规划的任务，再说明
dp[i]表示什么。
参考答案
适合动态规划。令
dp[i]表示凑出金额i所需的最少硬币数。 对于每枚不超过i的硬币c，都可以把dp[i-c] + 1作为候选答案， 再从这些候选值中取最小值。不同选择会反复遇到同一金额，较大金额的最优解也能由较小金额的最优解构成。 金额 6 的答案是 2，即3 + 3。应使用回溯。题目要求逐个生成全部 6 个排列，回溯可以系统地尝试一个选择、继续搜索， 再撤销选择并尝试其他分支。无论采用什么方法，实际输出这些排列时都不能跳过枚举。
使用循环或等差数列公式即可。虽然能写出
S(i) = S(i-1) + i，但计算S(i)时只依赖一个更小的S(i-1)， 每个部分和只需计算一次，不存在重复子问题，因此无需建立dp表。“能写递推式”不等于“需要动态规划”。
背包表中的一个格子怎么算
0-1 背包：物品重量 wgt = [1, 2, 3] ，价值 val = [5, 11, 15] ，背包容量 4 。
dp[i][c] 表示只考虑前 $i$ 件物品、背包容量上限为 $c$ 时，能够取得的最大价值；
不要求恰好装满背包。
现在只计算状态 dp[3][4]。已知 dp[2][4] = 16、dp[2][1] = 5：
- 不选第 3 件物品时，候选价值是多少？
- 选择第 3 件物品时，还剩多少容量，候选价值是多少？
dp[3][4]应取多少？对应选择了哪些物品？
参考答案
不选第 3 件物品时，沿用前两件物品的结果，候选价值为
dp[2][4] = 16。第 3 件物品重量为 3，放入后还剩容量 $4-3=1$；候选价值为
dp[2][1] + 15 = 5 + 15 = 20。比较 16 和 20，得到
dp[3][4] = 20。它对应选择第 1、3 件物品， 总重量为 $1+3=4$，总价值为 $5+15=20$。这个状态的计算体现了 0-1 背包的一次“选或不选”比较。
背包容量应该按什么顺序更新
一个 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] = 10。
dp[4] = 10这个结果是否正确？为什么？- 根据“每件物品最多选择一次”的条件，
dp[4]应为多少？ - 处理每件物品时，容量应从大到小还是从小到大更新？这样做避免了什么问题？
参考答案
这个结果不正确。价值 10 相当于把这件价值为 5 的物品放入了两次， 违反了“每件物品最多选择一次”的条件。
背包中最多只能放入这一件物品，所以正确的
dp[4]为 5。容量应从大到小更新，即依次处理 4、3、2。 这样在计算
dp[c]时，所读取的dp[c-2]仍是处理当前物品之前的结果， 不会在同一轮中重复使用当前物品。
编程练习
爬楼梯的方案数
一段楼梯共有 n 阶。你每次只能向上走 1 阶或 2 阶，且必须恰好到达第 n 阶。
请计算共有多少种不同的走法。规定 n >= 1，走法只按每一步走 1 阶还是 2 阶来区分。
请使用一维动态规划数组完成，暂不使用只保留两个状态的空间优化写法。
解题提示
- 到达第 i 阶的最后一步，只可能跨 1 阶或 2 阶
- 因此有 dp[i] = dp[i-1] + dp[i-2]
- 先处理 n 为 1 和 2 的情况，再从第 3 阶开始填表
说明： 题解讲解了一维 dp 状态和转移，但给出的代码采用滚动变量压缩空间；本练习要求先实现一维 dp 表，滚动变量仅作为选做优化
0-1 背包
给定等长数组 wgt 和 val，第 i 件物品的重量为正整数 wgt[i]、价值为非负整数 val[i]，
背包容量 cap 为非负整数。每件物品最多选择一次，请在总重量不超过 cap 的条件下，
求能够装入背包的最大总价值。请使用一维动态规划实现。
解题提示
- 初始化长度为 cap + 1 的数组 dp，其中 dp[c] 表示容量上限为 c 时的最大价值
- 处理物品 i 时，比较“不选它”的 dp[c] 与“选它”的 dp[c-wgt[i]] + val[i]
- 容量必须从大到小更新，避免在同一轮中重复选择当前物品