01背包问题 动态规划：从二维DP到一维滚动数组，空间复杂度 O(mn) 降至 O(m)

01背包问题动态规划：从二维DP到一维滚动数组的空间优化艺术

背包问题作为动态规划领域的经典案例，一直是算法学习者必须攻克的难关。特别是01背包问题，它不仅考察对动态规划核心思想的理解，更考验我们优化算法空间复杂度的能力。本文将带你深入探索01背包问题的两种解法——二维DP和一维滚动数组，并重点剖析状态转移方程从二维压缩到一维的数学原理，以及为何必须采用倒序遍历这一关键细节。

1. 01背包问题基础概念与二维DP解法

01背包问题的描述很简单：给定一个容量为W的背包和N个物品，每个物品有重量w_i和价值v_i。要求选择若干物品装入背包，使得背包中物品的总价值最大，且总重量不超过背包容量。这里的"01"意味着每个物品要么完整放入（1），要么不放入（0），不能分割。

1.1 二维DP的状态定义

我们定义一个二维数组dp[i][j]，表示考虑前i个物品，在背包容量为j时能获得的最大价值。这个定义是解决01背包问题的核心：

• i：考虑前i个物品（从1到N）
• j：当前背包的剩余容量（从0到W）

初始条件很直观：

• dp[0][j] = 0：考虑0个物品时，无论背包容量多大，价值都是0
• dp[i][0] = 0：背包容量为0时，无论考虑多少物品，价值都是0

1.2 状态转移方程

对于每个物品i，我们有两种选择：

1. 不放入背包：dp[i][j] = dp[i-1][j]
2. 放入背包（前提是j ≥ w_i）：dp[i][j] = dp[i-1][j-w_i] + v_i

因此，完整的状态转移方程为：

if j >= w[i]: dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) else: dp[i][j] = dp[i-1][j]

1.3 二维DP的代码实现

以下是Python实现的二维DP解法：

def knapsack_2d(W, wt, val): n = len(wt) dp = [[0]*(W+1) for _ in range(n+1)] for i in range(1, n+1): for j in range(1, W+1): if j >= wt[i-1]: dp[i][j] = max(dp[i-1][j], dp[i-1][j-wt[i-1]] + val[i-1]) else: dp[i][j] = dp[i-1][j] return dp[n][W]

这个解法的时间复杂度是O(NW)，空间复杂度也是O(NW)。对于较大的N和W，空间消耗会成为问题。

2. 一维滚动数组优化原理

观察二维DP的状态转移方程，我们会发现一个关键性质：计算dp[i][j]时，只依赖于上一行dp[i-1][...]的值。这意味着我们不需要存储整个二维数组，只需要维护前一行的数据即可。

2.1 空间优化思路

我们可以将二维数组压缩为一维数组dp[j]，其中：

• dp[j]表示背包容量为j时的最大价值
• 在计算新的dp[j]时，利用之前计算的结果

关键点在于遍历顺序——必须倒序更新dp数组。这是01背包问题优化的核心技巧。

2.2 为什么需要倒序遍历

正序遍历会导致一个物品被重复计算多次（这实际上是完全背包问题的解法）。我们需要确保在计算dp[j]时，dp[j-w[i]]还没有被当前物品更新过。

倒序遍历保证了：

1. 计算dp[j]时，dp[j-w[i]]仍然是上一轮（i-1时）的结果
2. 每个物品只被考虑一次

2.3 一维DP的代码实现

def knapsack_1d(W, wt, val): n = len(wt) dp = [0]*(W+1) for i in range(n): for j in range(W, wt[i]-1, -1): dp[j] = max(dp[j], dp[j-wt[i]] + val[i]) return dp[W]

这个版本的空间复杂度降到了O(W)，大大节省了内存。

3. 倒序遍历的数学本质与通用法则

3.1 状态依赖关系分析

理解倒序遍历的关键在于分析状态转移的依赖关系：

3.2 通用遍历顺序判断法则

对于动态规划问题的空间优化，可以遵循以下法则判断遍历顺序：

1. 分析状态转移方程中依赖的子状态位置
2. 如果当前状态依赖于"更早"的子状态（如dp[i-1][j-k]），使用倒序
3. 如果依赖于"已更新"的子状态（如dp[i][j-k]），使用正序

对于01背包问题，状态转移方程：

dp[j] = max(dp[j], dp[j-w[i]] + v[i])

这里dp[j-w[i]]必须在dp[j]之前计算且保持为上一轮的值，因此必须倒序。

4. 实战案例与常见误区

4.1 典型输入输出示例

考虑以下测试用例：

W = 10 wt = [2, 3, 4, 5] val = [3, 4, 5, 6]

二维DP和一维DP都应该返回最大价值13（选择第1、2、4件物品）。

4.2 常见错误与调试技巧

1. 正序遍历错误：会导致物品被重复计算

   • 表现：结果大于预期最大值
   • 解决方法：改为倒序

2. 边界条件处理不当：

   • 忘记初始化dp[0] = 0
   • 内层循环的终止条件错误

3. 索引混淆：

   • Python中列表从0开始，而问题描述常从1开始
   • 确保wt和val的索引一致

4.3 性能对比

在实际编程竞赛中，一维DP通常是首选，除非需要还原具体的选择路径。

5. 扩展应用与变种问题

虽然本文聚焦于空间优化，但01背包的思想可以扩展到许多变种问题：

1. 恰好装满问题：要求背包必须恰好装满

   • 初始化时dp[0]=0，其余为-∞

2. 方案计数问题：计算达到最大价值的方案数

   • 维护一个额外的计数数组

3. 多维限制问题：除了重量，还有体积等限制

   • 使用多维DP数组

4. 分组背包问题：物品属于不同组，每组只能选一个

这些变种都可以借鉴01背包的优化思路，根据具体状态转移方程调整遍历顺序和空间优化策略。

掌握01背包问题的空间优化技巧，不仅能够应对算法竞赛中的相关问题，更能深刻理解动态规划中状态压缩的精髓。记住关键点：分析状态依赖关系，正确选择遍历顺序，一维数组+倒序遍历是01背包空间优化的标准解法。