在 0/1 背包问题中，使用一维 DP 数组时必须逆序遍历背包容量，主要原因在于避免同一物品被重复计算。这与二维 DP 的实现方式有本质区别。下面通过公式和例子详细说明。
为什么一维 DP 必须逆序遍历？
状态定义
一维 DP 数组定义为：
$$ dp[j] = \text{背包容量为 } j \text{ 时的最大价值} $$状态转移方程
对于物品 $i$（重量 $w_i$，价值 $v_i$）：
$$ dp[j] = \max(dp[j], dp[j-w_i] + v_i) \quad (j \geq w_i) $$关键问题
- 正序遍历会导致 $dp[j-w_i]$ 在更新 $dp[j]$ 时已被当前物品更新过，相当于重复使用该物品。
- 逆序遍历保证 $dp[j-w_i]$ 始终是**上一轮（未考虑当前物品）**的结果，符合 0/1 背包的“一次性”规则。
二维 DP 为何不需要逆序？
二维 DP 定义为：
$$ dp[i][j] = \text{前 } i \text{ 个物品，容量 } j \text{ 时的最大价值} $$ 状态转移： $$ dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w_i] + v_i) $$ - 由于直接依赖 **上一行 $dp[i-1][\cdot]$**，不存在状态覆盖问题，正序/逆序均可。例子演示
假设物品 $w=2$, $v=3$，背包容量 $C=5$。
错误的正序遍历（$j=2 \to 5$）
- $j=2$:
$dp[2] = \max(0, dp[0]+3) = 3$
$\Rightarrow dp = [0, 0, 3, 0, 0, 0]$ - $j=4$:
$dp[4] = \max(0, dp[2]+3) = 6$
$\Rightarrow$ 错误：物品被重复使用两次！
正确的逆序遍历（$j=5 \to 2$）
- $j=5$:
$dp[5] = \max(0, dp[3]+3) = 0$ （$dp[3]$ 未更新） - $j=2$:
$dp[2] = \max(0, dp[0]+3) = 3$
$\Rightarrow dp = [0, 0, 3, 3, 3, 0]$
正确：物品仅使用一次。
总结
| 维度 | 遍历顺序 | 原因 |
|---|---|---|
| 一维DP | 逆序 | 防止 $dp[j-w_i]$ 被当前物品污染，确保每个物品只计算一次。 |
| 二维DP | 任意顺序 | 状态分层存储（$dp[i][j]$ 只依赖 $dp[i-1][\cdot]$），无覆盖风险。 |
核心思想：一维 DP 的空间优化需要逆序来保证状态的无后效性。