二维dpi定义最稳妥，因逻辑清晰、不易出错；初始化全0即可满足边界条件；转移时需判断j≥weight[i-1]避免越界；一维优化须倒序遍历以防重复选取。
为什么 dp[i][j] 定义成「前 i 个物品、容量为 j 时的最大价值」最稳妥
很多初学者会尝试用 dp[j] 一维数组直接推，但容易搞错遍历顺序或覆盖未使用的状态。二维定义虽然多占空间，但逻辑清晰、不易出错，尤其在调试和理解转移关系时更可靠。
关键点在于：每个物品只能选 0 次或 1 次，所以状态转移必须区分「不选第 i 个」和「选第 i 个」两种情况：
- 不选：
dp[i-1][j] - 选（前提是
j >= weight[i-1]）：dp[i-1][j - weight[i-1]] + value[i-1]
注意物品数组通常从 0 开始索引，所以第 i 个物品对应 weight[i-1] 和 value[i-1]。
如何正确初始化 dp 数组并避免越界访问
初始化时，dp[0][j] 表示「前 0 个物品」能装下的最大价值，显然全为 0；dp[i][0] 表示「容量为 0」时的价值，也全为 0。但实际编码中，只要把整个 dp 数组初始化为 0，就能自然满足这两个边界条件。
立即学习“C++免费学习笔记（深入）”；
真正容易出错的是状态转移中的下标检查：
- 必须判断
j >= weight[i-1]才能尝试选择第 i 个物品，否则跳过 - 二维数组大小应为
(n+1) x (W+1)，其中n是物品数量，W是背包容量 - 如果用
vector<vector>></vector>，记得先 resize 正确维度，否则运行时可能崩溃
一维优化版 dp[j] 的核心约束和遍历方向
一维写法节省空间，但必须倒序遍历容量 j（从 W 到 weight[i-1]），否则会重复使用刚更新过的值，导致一个物品被多次选取（退化成完全背包）。
常见错误现象：dp[W] 结果明显偏大，甚至超过所有物品价值之和——大概率是正向遍历了 j。
实操建议：
- 初始化
vector<int> dp(W+1, 0)</int> - 外层循环
i从 0 到n-1 - 内层循环
j从W降序到weight[i]（含） - 转移式：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
#include <vector>
#include <algorithm>
using namespace std;
<p>int knapsack01(const vector<int>& weight, const vector<int>& value, int W) {
int n = weight.size();
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));</p><pre class='brush:php;toolbar:false;'>for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= W; ++j) {
dp[i][j] = dp[i-1][j]; // 不选第 i 个
if (j >= weight[i-1]) {
dp[i][j] = max(dp[i][j], dp[i-1][j - weight[i-1]] + value[i-1]);
}
}
}
return dp[n][W];}
一维优化看似简洁，但一旦数据规模变大或需要输出具体选了哪些物品，二维结构反而更容易回溯路径。别为了省几 MB 内存，让逻辑变得脆弱。
