01背包问题（二维动态规划法）的时间复杂度与空间复杂度
摘要
本文分析01背包问题的二维动态规划解法。定义物品数量为N、背包容量为W，状态dp[i][j]表示前i件物品在容量j下的最大价值。通过双重循环填充(N+1)×(W+1)表格，每格O(1)计算，得到时间复杂度O(N×W)；存储完整二维数组，空间复杂度同为O(N×W)。代码示例采用Java实现。文末补充一维滚动数组优化可将空间降至O(W)，但时间复杂度不变。本文重点阐明复杂度指标与符号含义，帮助读者清晰理解二维DP的性能瓶颈。
ps：图片来源网络，侵删
目录
一、先给结论（开门见山）
二、问题定义与符号说明
三、二维DP解法详解
1. 状态定义
2. 状态转移方程
3. 边界条件
四、时间复杂度分析（核心）
五、空间复杂度分析（核心）
六、二维DP完整代码示例（Java）
七、关于一维空间优化的补充（仅为提及）
总结
一、先给结论（开门见山）
对于01背包问题，使用二维动态规划（DP）求解时：
时间复杂度为：O(N × W)
空间复杂度为：O(N × W)
其中，
N代表物品的总个数，W代表背包的最大容量（即最大承重/体积）。这两个符号将贯穿全文。
二、问题定义与符号说明
给定N件物品，编号从 1 到N。第i件物品的重量为weight[i]，价值为value[i]。现有背包的最大承重为W。每件物品只能选择放入（1）或放弃（0），求解在不超过背包承重的前提下，背包内物品的最大总价值是多少。
符号约定：
N：物品的数量W：背包的容量限制（最大承重）weight[i]：第i件物品的重量value[i]：第i件物品的价值
三、二维DP解法详解
1. 状态定义
我们定义一个二维数组dp[i][j]，其含义为：
只考虑前
i件物品（即第 1 到第i件），在背包当前承重上限为j的情况下，能够获得的最大总价值。
其中，i的取值范围是[0, N]，j的取值范围是[0, W]。
2. 状态转移方程
面对第i件物品（重量weight[i]，价值value[i]），我们只有两种选择：
不选第
i件物品：那么当前最大价值就等于前i-1件物品在容量j下的最大价值，即dp[i-1][j]。选第
i件物品：前提是当前容量j必须 ≥weight[i]，此时背包剩余容量变为j - weight[i]，价值为前i-1件物品在该剩余容量下的最大价值加上当前物品价值，即dp[i-1][j - weight[i]] + value[i]。
综合两者，取最大值，转移方程为：
当 j < weight[i] 时： dp[i][j] = dp[i-1][j] 当 j ≥ weight[i] 时： dp[i][j] = max( dp[i-1][j], dp[i-1][j - weight[i]] + value[i] )3. 边界条件
当
i = 0时（没有物品），任何容量下的价值都是 0：dp[0][j] = 0当
j = 0时（背包容量为0），任何物品都放不下，价值也是 0：dp[i][0] = 0
四、时间复杂度分析（核心）
我们采用双层嵌套循环来填充这个(N+1) × (W+1)的二维表格：
外层循环：遍历每一件物品，
i从 1 到N，共循环N次。内层循环：遍历背包容量的每一个刻度，
j从 0 到W，共循环W + 1次（复杂度量级记作W次）。
在循环体的内部，无论是判断语句if (j < weight[i])，还是求最大值的操作max()，都只涉及基本的比较和整数加法，这些操作均属于常数时间，即O(1)。
因此，程序运行所需的总基本操作次数为：
总次数 = N × W × O(1)
忽略常数项后，得出时间复杂度为：
T(N, W) = O(N × W)
特别注意：这是一个伪多项式时间复杂度。因为W在计算机中是以二进制长度存储的数值，其数值大小是指数级的。但在算法竞赛和常规面试中，我们默认将N和W看作输入规模，并以此作为复杂度衡量标准。
五、空间复杂度分析（核心）
二维DP解法需要维护一个完整的二维数组dp[N+1][W+1]。
该数组总共包含(N + 1) × (W + 1)个元素。在大多数编程语言（如 C++、Java、Python）中，每个元素存储一个整型数值（通常占 4 或 8 个字节）。为了衡量数量级，我们忽略常数系数和低阶项，得到数组占用的总空间为：
总空间 = (N+1) × (W+1) ≈ N × W
因此，空间复杂度为：
S(N, W) = O(N × W)
当N = 1000，W = 1000时，数组大小约为 100 万个单位，内存尚可接受；但当N = 10^4，W = 10^4时，数组将膨胀到 1 亿个单位，内存占用将变得非常可观（约 400 MB 以上），这也是二维DP的主要瓶颈所在。
六、二维DP完整代码示例（Java）
public class Knapsack2D { public static int knapsack2D(int N, int W, int[] weight, int[] value) { // 初始化二维DP表，默认值为0 int[][] dp = new int[N + 1][W + 1]; // 遍历每一件物品 for (int i = 1; i <= N; i++) { for (int j = 0; j <= W; j++) { // 1. 默认不选第i件物品 dp[i][j] = dp[i - 1][j]; // 2. 如果容量足够，尝试选第i件物品，取最大值 if (j >= weight[i]) { dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weight[i]] + value[i]); } } } // 返回前N件物品、容量W下的最大价值 return dp[N][W]; } public static void main(String[] args) { int N = 4, W = 8; // 下标从1开始，占位0 int[] weight = {0, 2, 3, 4, 5}; int[] value = {0, 3, 4, 5, 6}; System.out.println("最大价值为：" + knapsack2D(N, W, weight, value)); } }七、关于一维空间优化的补充（仅为提及）
由于dp[i][j]的状态转移只依赖于上一行dp[i-1][...]的数据，因此我们可以将二维数组压缩为一维数组（滚动数组），将空间复杂度优化为 O(W)。
但必须注意，压缩为一维后，内层循环j必须采用逆序（从W递减到weight[i]）遍历，以防止同一件物品被重复累加。尽管如此，时间复杂度的量级并不会改变，依然为O(N × W)。
总结
| 实现方式 | 时间复杂度 | 空间复杂度 | 核心依赖 |
|---|---|---|---|
| 二维DP | O(N × W) | O(N × W) | 完整的二维状态表 |
| 一维DP（优化） | O(N × W) | O(W) | 逆序滚动数组 |
再次强调，本文重点讨论的二维DP，其时间复杂度O(N × W)由双重循环决定，空间复杂度O(N × W)由二维数组大小决定。其中N是物品个数，W是背包容量（重量限制）。希望这次严格按照符号规范的讲解，能帮您彻底理清这两个指标！如有疑问，欢迎留言讨论。