跳转至
纸质书已发行，详情请见这里

# 14.8 练习

## 14.8.1 知识巩固

### 1. 什么时候适合使用动态规划

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

1. 使用面值 `[1, 3, 4]` 的硬币凑出金额 6，求最少硬币数，每种硬币可重复使用；
2. 输出 `[1, 2, 3]` 的全部排列；

3. 计算 \(1 + 2 + \dots + n\)。

   对于你判断为适合动态规划的任务，再说明 `dp[i]` 表示什么。

参考答案

1. 适合动态规划。令 `dp[i]` 表示凑出金额 `i` 所需的最少硬币数。 对于每枚不超过 `i` 的硬币 `c`，都可以把 `dp[i-c] + 1` 作为候选答案， 再从这些候选值中取最小值。不同选择会反复遇到同一金额，较大金额的最优解也能由较小金额的最优解构成。 金额 6 的答案是 2，即 `3 + 3`。

2. 应使用回溯。题目要求逐个生成全部 6 个排列，回溯可以系统地尝试一个选择、继续搜索， 再撤销选择并尝试其他分支。无论采用什么方法，实际输出这些排列时都不能跳过枚举。

3. 使用循环或等差数列公式即可。虽然能写出 `S(i) = S(i-1) + i`，但计算 `S(i)` 时只依赖一个更小的 `S(i-1)`， 每个部分和只需计算一次，不存在重复子问题，因此无需建立 `dp` 表。“能写递推式”不等于“需要动态规划”。

### 2. 背包表中的一个格子怎么算

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`：

1. 不选第 3 件物品时，候选价值是多少？
2. 选择第 3 件物品时，还剩多少容量，候选价值是多少？
3. `dp[3][4]` 应取多少？对应选择了哪些物品？

参考答案

1. 不选第 3 件物品时，沿用前两件物品的结果，候选价值为 `dp[2][4] = 16`。

2. 第 3 件物品重量为 3，放入后还剩容量 \(4-3=1\)；候选价值为 `dp[2][1] + 15 = 5 + 15 = 20`。

3. 比较 16 和 20，得到 `dp[3][4] = 20`。它对应选择第 1、3 件物品， 总重量为 \(1+3=4\)，总价值为 \(5+15=20\)。

   这个状态的计算体现了 0-1 背包的一次“选或不选”比较。

### 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] = 10`。

1. `dp[4] = 10` 这个结果是否正确？为什么？
2. 根据“每件物品最多选择一次”的条件，`dp[4]` 应为多少？
3. 处理每件物品时，容量应从大到小还是从小到大更新？这样做避免了什么问题？

参考答案

1. 这个结果不正确。价值 10 相当于把这件价值为 5 的物品放入了两次， 违反了“每件物品最多选择一次”的条件。

2. 背包中最多只能放入这一件物品，所以正确的 `dp[4]` 为 5。

3. 容量应从大到小更新，即依次处理 4、3、2。 这样在计算 `dp[c]` 时，所读取的 `dp[c-2]` 仍是处理当前物品之前的结果， 不会在同一轮中重复使用当前物品。

## 14.8.2 编程练习

### 1. 爬楼梯的方案数

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

解题提示

1. 到达第 i 阶的最后一步，只可能跨 1 阶或 2 阶
2. 因此有 dp[i] = dp[i-1] + dp[i-2]
3. 先处理 n 为 1 和 2 的情况，再从第 3 阶开始填表

LeetCode 题目解析

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

### 2. 0-1 背包

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

解题提示

1. 初始化长度为 cap + 1 的数组 dp，其中 dp[c] 表示容量上限为 c 时的最大价值
2. 处理物品 i 时，比较“不选它”的 dp[c] 与“选它”的 dp[c-wgt[i]] + val[i]
3. 容量必须从大到小更新，避免在同一轮中重复选择当前物品

##### 欢迎在评论区留下你的见解、问题或建议