引言 (Introduction)
背包问题（Knapsack Problem）是 DP 领域最具代表性、也最常被考察的问题族。从 0/1 背包到完全背包再到多重背包，它们的转移方程高度相似，却因为一个循环顺序的改变而产生本质差异。
本文是本系列第三篇。在掌握了一维和二维 DP 的基础建模之后，我们将以背包问题为载体，学习空间优化与循环顺序对语义的影响这两个 DP 的核心进阶技巧。
1. 0/1 背包：选或不选
1.1 问题定义
给定 $n$ 件物品，每件重量 $w_i$、价值 $v_i$。背包容量为 $W$。每件物品最多选一次。求能装入背包的最大总价值。
1.2 二维定义
$dp[i][w]$：考虑前 $i$ 件物品，容量为 $w$ 时的最大价值。
转移方程：
$$dp[i][w] = \max\begin{cases} dp[i-1][w] & \text{不选第 } i \text{ 件} \\ dp[i-1][w - w_i] + v_i & \text{选第 } i \text{ 件（前提 } w \ge w_i\text{）} \end{cases}$$边界：$dp[0][*] = 0$（没有物品可选），$dp[*][0] = 0$（容量为 0）。
1.3 空间优化：二维 → 一维
观察转移方程：$dp[i][w]$ 只依赖上一行 $(i-1)$ 的 $w$ 和 $w - w_i$ 位置。如果我们只用一维数组，需要保证「上一行的值」不会被「当前行的值」覆盖。
关键技巧：容量倒序遍历。如果正序（$0 \to W$），$dp[w - w_i]$ 可能已经被当前行更新过，导致一件物品被多次使用（变成了完全背包）。倒序遍历保证 $dp[w - w_i]$ 仍然是上一行的值。
from typing import List
def knapsack_01(weights: List[int], values: List[int], W: int) -> int:
n = len(weights)
dp: List[int] = [0] * (W + 1)
for i in range(n):
# 倒序：保证每件物品只用一次
for w in range(W, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]
复杂度：时间 $O(nW)$，空间 $O(W)$。
1.4 为什么倒序就等于 0/1？
正序（错误）：
dp[2] 用到了 dp[1]（当前行刚更新）
dp[3] 用到了 dp[2]（当前行刚更新）
→ 一件物品被用了多次
倒序（正确）：
dp[5] 用到 dp[3]（上一行的旧值）
dp[4] 用到 dp[2]（上一行的旧值）
→ 每件物品只用一次
一图胜千言：正序是「同一行内的自我引用」，倒序是「上一行的跨行引用」。
2. 完全背包：每件物品无限用
2.1 转移方程差异
完全背包（Unbounded Knapsack）中每件物品可以用任意多次。二维转移方程变为：
$$dp[i][w] = \max(dp[i-1][w],\ dp[i][w - w_i] + v_i)$$注意第二个参数：$dp[i][w - w_i]$ 而非 $dp[i-1][w - w_i]$。因为选了第 $i$ 件物品后，还可以继续选第 $i$ 件（仍在当前行）。
2.2 空间优化：正序即可
在一维数组中，完全背包只需将内循环改为正序：
from typing import List
def knapsack_unbounded(weights: List[int], values: List[int], W: int) -> int:
n = len(weights)
dp: List[int] = [0] * (W + 1)
for i in range(n):
# 正序：允许同一物品多次使用
for w in range(weights[i], W + 1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]
2.3 0/1 vs 完全——一图总结
0/1 背包 完全背包
───────── ─────────
内层循环: 倒序 (W → w_i) 正序 (w_i → W)
语义: dp[w-w_i] = 上一行旧值 dp[w-w_i] = 当前行新值
结果: 每件最多选一次 每件可选无限次
3. 循环顺序决定「组合」还是「排列」
这是背包问题中最容易被忽视、也最常被问到的一个知识点。
3.1 两种循环顺序
顺序 A：外层物品，内层容量
for coin in coins: # 外层：物品
for amount in range(coin, target + 1): # 内层：容量
dp[amount] += dp[amount - coin]
语义：求的是组合数（Combination）。{1, 2} 和 {2, 1} 被视为同一种方案，因为硬币的遍历顺序固定。
顺序 B：外层容量，内层物品
for amount in range(1, target + 1): # 外层：容量
for coin in coins: # 内层：物品
if amount >= coin:
dp[amount] += dp[amount - coin]
语义：求的是排列数（Permutation）。{1, 2} 和 {2, 1} 被视为不同的方案，因为每个容量下硬币的遍历顺序不固定。
3.2 直觉解释
外层物品、内层容量：每个硬币只被"考虑"一次，在遍历到它时，它只能出现在当前决策的末尾。因此顺序固定 → 组合数。
外层容量、内层物品：在同一个 amount 下，所有硬币都会被考虑。dp[amount - 1] 中包含了以 2 结尾的方案，dp[amount - 2] 中包含了以 1 结尾的方案——两种结尾都会出现 → 排列数。
接下来的 LeetCode 518 和下一篇文章的 377（组合总和 IV）将分别实践这两种循环顺序。
4. LeetCode 416：分割等和子集
题目：给定数组 nums，判断能否将其分成两个和相等的子集。
4.1 问题转化
能否选出若干数，使它们的和等于 $\frac{1}{2} \sum nums$？如果总和为奇数，直接返回 False。这就是一个 0/1 背包问题：每件物品的重量 = 价值 = nums[i]，背包容量 = target，判断能否恰好装满。
4.2 完整代码
from typing import List
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp: List[bool] = [False] * (target + 1)
dp[0] = True # 容量为 0 始终可行
for num in nums:
for w in range(target, num - 1, -1): # 0/1 背包：倒序
dp[w] = dp[w] or dp[w - num]
return dp[target]
复杂度：时间 $O(n \cdot target)$，空间 $O(target)$。
如果把 dp 类型从 bool 改为 int 来记录方案数，那就是 494（目标和）的解法——这正是背包模型的可迁移性。
5. LeetCode 322：零钱兑换
题目：给定硬币面值 coins 和总金额 amount，每种硬币无限使用，求凑成 amount 的最少硬币数。若不可能则返回 -1。
5.1 完全背包变形
标准完全背包求最大价值，这里求最小硬币数。转移方程：
$$dp[w] = \min(dp[w],\ dp[w - coin] + 1)$$初始化：$dp[0] = 0$，其余 $dp[w] = \infty$（或 amount + 1）。
5.2 完整代码
from typing import List
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
INF = amount + 1
dp: List[int] = [INF] * (amount + 1)
dp[0] = 0
for coin in coins: # 外层：硬币
for w in range(coin, amount + 1): # 内层：容量（正序 = 完全背包）
dp[w] = min(dp[w], dp[w - coin] + 1)
return dp[amount] if dp[amount] != INF else -1
复杂度：时间 $O(n \cdot amount)$，空间 $O(amount)$。
5.3 为什么是 BFS 的 DP 变体？
零钱兑换也可以用 BFS 求解（将金额看作图的节点，硬币是边权）。DP 解法本质上是 BFS 在 DAG（有向无环图）上的最短路径。DP 填表过程等价于对金额递增做拓扑排序。这个联系说明了为什么 DP 和最短路径算法（Dijkstra、Bellman-Ford）之间有深刻的同构关系。
6. LeetCode 518：零钱兑换 II
题目：给定硬币面值 coins 和总金额 amount，每种硬币无限使用，求凑成 amount 的不同组合数。
6.1 循环顺序的关键作用
题目要求组合数（即 {1, 2} 和 {2, 1} 算同一种），因此必须使用「外层硬币、内层容量」的循环顺序。
from typing import List
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp: List[int] = [0] * (amount + 1)
dp[0] = 1 # 凑 0 元有 1 种方案：什么都不选
for coin in coins: # 外层：硬币（保证顺序固定）
for w in range(coin, amount + 1): # 内层：容量（正序）
dp[w] += dp[w - coin]
return dp[amount]
复杂度：时间 $O(n \cdot amount)$，空间 $O(amount)$。
6.2 如果改成排列数？
如果题目要求排列数（即 {1, 2} 和 {2, 1} 算两种），只需交换循环顺序：
for w in range(1, amount + 1): # 外层：容量
for coin in coins: # 内层：硬币
if w >= coin:
dp[w] += dp[w - coin]
这就是 LeetCode 377（组合总和 IV）的解法。注意虽然题目名称里叫"组合"，但实际上是排列——这是 LeetCode 的一个命名误导。
7. 背包问题族一览
| 变体 | 约束 | 内层循环方向 | 典型题目 |
|---|---|---|---|
| 0/1 背包 | 每件最多选一次 | 倒序 W → w_i |
416 分割等和子集 |
| 完全背包 | 每件可选无限次 | 正序 w_i → W |
322 零钱兑换、518 零钱兑换 II |
| 组合数 | 顺序无关 | 外层物品、内层容量 | 518 零钱兑换 II |
| 排列数 | 顺序有关 | 外层容量、内层物品 | 377 组合总和 IV |
结论 (Conclusion)
本文攻克了 DP 领域最经典的背包问题族。核心收获：
- 0/1 vs 完全：差别仅在内层循环的方向——倒序保证每件只用一次（引用上一行），正序允许重复使用（引用当前行）。
- 组合 vs 排列：差别仅在内外层循环的顺序——外层物品固定了物品的选取顺序，形成组合；外层容量让物品顺序自由，形成排列。
- 背包建模能力：三道题（416、322、518）覆盖了「可行性」「最值」「计数」三种 DP 目标类型，这些模型可以迁移到大量同类题目中。
下一篇预览：子序列与字符串 DP——最长公共子序列（LCS）、最长递增子序列（LIS）的 $O(n \log n)$ 优化、编辑距离、回文子串的区间 DP 建模（LeetCode 1143、300、72、5）。