std::vector比裸数组更适合背包dp，因其自动管理堆内存、支持动态resize、避免栈溢出和初始化遗漏；一维优化用vector dp(w+1,0)，二维用vector dp(n+1,vector(w+1,0))。
为什么 std::vector 比裸数组更适合写背包 DP
因为背包问题需要频繁访问「前一层状态」，而动态规划的二维递推（比如 dp[i][w]）在 C++ 里容易因栈溢出或手动内存管理翻车。用 std::vector 能自动管理堆内存，且支持按需 resize，避免越界或初始化遗漏。
实操建议：
- 一维优化时用
std::vector<int> dp(W + 1, 0)</int>，别手写int dp[10005]—— W 大于 1e5 就炸栈 - 二维原始写法优先用
std::vector<:vector>> dp(N + 1, std::vector<int>(W + 1, 0))</int></:vector>，别用new int*[N]手动二维指针，析构麻烦还易漏 - 初始化值要对齐语义：01 背包求最大价值填
0；恰好装满型必须填INT_MIN（除dp[0] = 0），否则无效状态会被错误转移
for (int w = W; w >= weight[i]; w--) 这个倒序到底在防什么
它防的是「同一件物品被重复使用」——也就是把 01 背包错写成完全背包。正序遍历 w 会让 dp[w - weight[i]] 已经是本轮更新过的值，相当于悄悄用了两次 i 物品。
常见错误现象：
立即学习“C++免费学习笔记（深入）”；
- 输入
weights = [2], W = 4，正序得到dp[4] = 2 * value[0]，但题目只给 1 个物品 - 调试时发现结果比预期大，尤其当所有
value[i]相同，会明显看出倍数关系 - 换成完全背包？那就改回正序，但得确认题干真允许无限取——很多 OJ 题面写“每种物品一个”，却有人默认能刷
空间优化后怎么还原具体选了哪些物品
一维 dp 数组不存路径信息，直接还原不了。必须保留决策过程，或者多开一维记录选择标记。
实操建议：
- 如果只要答案值，坚持一维节省空间；如果要输出方案，老老实实用二维
dp[i][w]，再加一个chosen[i][w]布尔数组记录「是否选了第 i 个」 - 更省内存的做法：用
std::vector<:vector>> chosen(N + 1, std::vector<bool>(W + 1))</bool></:vector>，每个chosen[i][w]表示在考虑前 i 个、容量为 w 时，是否选了第 i 个 - 还原时从
i = N, w = W往回推：若chosen[i][w]为真，则加入第 i 个，并令w -= weight[i-1]（注意下标偏移）
LeetCode 416 和 AcWing 2.01 背包的输入差异怎么影响写法
LeetCode 416 是「分割等和子集」，本质是 01 背包判断能否恰好装满 sum / 2；AcWing 2.01 是标准输入格式（先 N W，再每行 weight value）。两者状态定义一致，但边界处理差很多。
关键差异点：
- LeetCode 416 不需要
value数组，weight[i]同时是体积和价值，目标是让总和恰好等于target，所以初始化要用dp[0] = true，其余false - AcWing 数据范围常带「多组测试」，记得每次清空
dp或重置为初始值，别用全局变量残留上一组结果 - 当
sum是奇数时，LeetCode 416 直接返回false；而 AcWing 若没这条件，可能卡在target = sum / 2下取整导致 WA
复杂点往往不在状态转移本身，而在题干对「恰好」「不超过」「最大价值」这些词的咬文嚼字，以及初始化时对无效状态的屏蔽方式——稍不注意，dp[0] 多设一个 1，整个表就全偏了。
