背包问题系列
背包问题是 DP 中的经典题型。面试官想看到的不是你会套模板，而是你能从问题中抽象出 DP 模型，理解为什么这样定义状态。
面试考察点
面试官通过这道题想考察：
1. 你是否能正确抽象出 DP 的状态
2. 你是否能理解"选"和"不选"的决策过程
3. 你是否能区分 0-1 背包和完全背包
4. 你是否能进行空间优化
一、0-1 背包问题
1.1 问题定义（小白解释）
面试官追问："什么是 0-1 背包？"
问题描述：
- 有一个容量为 W 的背包
- 有 n 件物品，每件物品有重量 w[i] 和价值 v[i]
- 每件物品只能选一次（0 或 1）
- 问：如何选择物品使得不超过容量 W 的情况下价值最大？
示例：
背包容量 W = 8
物品：
A: 重量 3，价值 30
B: 重量 4，价值 50
C: 重量 5，价值 60
选择 A+B：重量 3+4=7，价值 30+50=80
选择 A+C：重量 3+5=8，价值 30+60=90 ✓
选择 B+C：重量 4+5=9，超了！
1.2 如何定义状态？（核心）
面试官追问："你怎么定义 DP 的状态？"
状态定义：
dp[i][j] = 考虑前 i 件物品，背包容量为 j 时的最大价值
为什么这样定义？
因为对于每件物品，我们只有两个选择：选或不选
关键理解：
dp[i][j] 依赖于 dp[i-1][j] 和 dp[i-1][j-w[i]]
- dp[i-1][j]：不选第 i 件物品
- dp[i-1][j-w[i]] + v[i]：选第 i 件物品（需要腾出 w[i] 的空间）
这就是"最优子结构"！
1.3 状态转移方程
dp[i][j] = max(
dp[i-1][j], // 不选第 i 件物品
dp[i-1][j-w[i]] + v[i] // 选第 i 件物品
)
边界条件：
- dp[0][j] = 0（没有物品可选）
- dp[i][0] = 0（容量为 0）
- j < w[i] 时，只能不选
1.4 图解过程
物品：重量 [3, 4, 5]，价值 [30, 50, 60]
容量 W = 8
填表过程：
dp[0][*] = 0（没有物品）
dp[*][0] = 0（容量为0）
填 dp[1][*]（考虑物品 A）：
- j=0..2: j < 3，只能不选，dp[1][j] = 0
- j=3: max(dp[0][3], dp[0][0]+30) = max(0, 30) = 30
- j=4: max(dp[0][4], dp[0][1]+30) = max(0, 30) = 30
...
- j=8: max(dp[0][8], dp[0][5]+30) = max(0, 30) = 30
填 dp[2][*]（考虑物品 A, B）：
- j=3: max(dp[1][3], dp[1][-1]+50) = max(30, -∞) = 30
- j=4: max(dp[1][4], dp[1][0]+50) = max(30, 50) = 50
- j=7: max(dp[1][7], dp[1][3]+50) = max(30, 30+50) = 80
- j=8: max(dp[1][8], dp[1][4]+50) = max(30, 50) = 50
最终 dp[3][8] 就是答案
二、0-1 背包的变形
2.1 分割等和子集（LeetCode 416）
考察点：0-1 背包的变形
问题：能否把数组分成两个和相等的子集？
转换：
- 总和 sum，如果能平分，每个子集和为 sum/2
- 问题变成：能否从数组中选若千元素，和为 sum/2？
这就是 0-1 背包！
- 背包容量 = sum/2
- 每件物品（数字）只能用一次
- 问：能否装满背包？
2.2 目标和（LeetCode 494）
考察点：状态定义的技巧
问题：在数组每个数前加 + 或 -，使结果等于 target
转换：
- 加 + 的数为 P，减 - 的数为 N
- P + N = sum
- P - N = target
- 解方程：P = (sum + target) / 2
问题变成：选出若干数，和为 P，有多少种选法？
这就是 0-1 背包的"计数"版本！
三、完全背包问题
3.1 和 0-1 背包的区别
面试官追问："完全背包和 0-1 背包有什么区别？"
0-1 背包：每件物品只能选一次
完全背包：每件物品可以选无限次
示例：
有硬币 1 元、2 元、5 元，要凑 10 元
0-1 背包：每种硬币只有 1 个
完全背包：每种硬币有无限个
在 DP 中：
- 0-1 背包：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
用上一行的状态（不重复选同一物品）
- 完全背包：dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v)
用本行的状态（可以重复选同一物品）
3.2 零钱兑换 II（LeetCode 518）
考察点：完全背包的计数问题
问题：凑成 amount 的硬币组合数
物品：硬币面额
背包容量：amount
每种硬币无限（完全背包）
状态定义：
dp[i] = 凑成金额 i 的方式数
状态转移：
dp[j] += dp[j - coin] for coin in coins
初始化：
dp[0] = 1（凑 0 元有一种方式：不选任何硬币）
四、面试总结
背包问题的本质
┌─────────────────────────────────────────────────┐
│ 背包问题 │
├─────────────────────────────────────────────────┤
│ │
│ 0-1 背包：每件物品只能选一次 │
│ 完全背包：每件物品可以选多次 │
│ │
│ 状态定义：dp[i][j] = 考虑前 i 件，容量 j 的最优 │
│ │
│ 0-1 背包转移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v) │
│ 完全背包转移：dp[i][j] = max(dp[i-1][j], dp[i][j-w]+v) │
│ │
│ 空间优化：dp[j] 从后往前（0-1） │
│ dp[j] 从前往后（完全） │
│ │
└─────────────────────────────────────────────────┘
面试能加分的回答
1. 能解释为什么这样定义状态
"对于每件物品只有选或不选两种情况"
2. 能解释状态转移
"选或不选，取价值更大的"
3. 能解释 0-1 和完全背包的区别
"0-1 用上一行状态，完全用本行状态"
4. 能解释空间优化
"因为 dp[j] 只依赖 dp[j-w]，可以压缩"
相关题目
- LeetCode 416 - 分割等和子集 - 0-1 背包变形
- LeetCode 494 - 目标和 - 0-1 背包变形
- LeetCode 518 - 零钱兑换 II - 完全背包