14.8 练习¶

14.8.1 知识巩固¶

一位同学说：“只要能写出递推式，就应该使用动态规划。” 请判断下面三个任务分别更适合使用动态规划、回溯，还是使用循环或数学公式而不建立 dp 表，并写出一个关键理由。

参考答案

适合动态规划。令 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 件物品时，沿用前两件物品的结果，候选价值为 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 更新：

参考答案

这个结果不正确。价值 10 相当于把这件价值为 5 的物品放入了两次，违反了“每件物品最多选择一次”的条件。
背包中最多只能放入这一件物品，所以正确的 dp[4] 为 5。
容量应从大到小更新，即依次处理 4、3、2。这样在计算 dp[c] 时，所读取的 dp[c-2] 仍是处理当前物品之前的结果，不会在同一轮中重复使用当前物品。

一段楼梯共有 n 阶。你每次只能向上走 1 阶或 2 阶，且必须恰好到达第 n 阶。请计算共有多少种不同的走法。规定 n >= 1，走法只按每一步走 1 阶还是 2 阶来区分。请使用一维动态规划数组完成，暂不使用只保留两个状态的空间优化写法。

解题提示

说明： 题解讲解了一维 dp 状态和转移，但给出的代码采用滚动变量压缩空间；本练习要求先实现一维 dp 表，滚动变量仅作为选做优化

给定等长数组 wgt 和 val，第 i 件物品的重量为正整数 wgt[i]、价值为非负整数 val[i]，背包容量 cap 为非负整数。每件物品最多选择一次，请在总重量不超过 cap 的条件下，求能够装入背包的最大总价值。请使用一维动态规划实现。

解题提示