01背包二维dp需声明dpn+1，dp0和dpi均初始化为0；完全背包与01背包区别仅在内层j循环方向：升序为完全背包（可重复选），降序为01背包（只选一次）。
01背包：二维DP数组怎么初始化才不会越界
二维DP解法最稳妥的初始化方式是让 dp[i][j] 表示「前 i 个物品、容量为 j 时的最大价值」，此时必须声明 dp[n+1][W+1]（n为物品数，W为背包容量），否则访问 dp[i-1][...] 会越界。
常见错误是把数组开成 dp[n][W] 然后循环从 i=0 开始，导致 dp[i-1] 访问非法内存；或者忘记初始化边界——dp[0][j] 全为 0（没物品当然没价值），dp[i][0] 也全为 0（容量为0装不下任何东西）。
关键细节：
- 物品索引从 0 开始，但 DP 状态 i 对应前 i 个物品，所以遍历物品时用
weights[i-1]和values[i-1] - 内层 j 循环必须从 0 到 W（含），不能只到 W−1
- 状态转移只依赖上一行，可空间优化，但初学建议先写清楚二维逻辑
完全背包：内层循环方向决定是“每种物品无限用”还是“只用一次”
完全背包和01背包代码长得几乎一样，唯一区别就在内层容量循环的方向：升序即完全背包，降序即01背包。这是因为升序时 dp[j - w] 可能已是本轮更新过的值，意味着当前物品可以重复选；而降序保证用的是上一轮的旧值，等效于只选一次。
容易踩的坑：
- 误以为只要改了循环方向就自动支持“无限”，其实前提是物品数组不重复传入、且状态定义仍是「前i个物品」
- 没有预判
j - w 的情况，导致数组下标负数——应在循环内加 <code>if (j >= w)判断 - 用
int dp[W+1]但未初始化为 0，残留垃圾值影响结果
示例片段（完全背包核心循环）：
for (int i = 0; i <h3>空间优化后如何还原具体选了哪些物品</h3><p>一维DP省空间，但丢掉了「逐行决策」信息，无法直接回溯路径。如果需要输出方案（比如打印选了哪几个物品），必须保留二维数组，或额外维护一个 <code>choice[i][j]</code> 数组记录决策（选/不选），或者用滚动数组+路径压缩技巧。</p><p>更实用的做法是：空间允许时直接用二维 <code>dp[i][j]</code>，回溯时从 <code>dp[n][W]</code> 倒推：</p>
- 若
dp[i][j] == dp[i-1][j]，说明第 i 个物品没选 - 否则它被选中，跳转到
dp[i-1][j - weights[i-1]]
注意：回溯用的是原始二维DP值，不是一维优化后的数组；而且完全背包的路径还原更复杂，因为同一物品可能被选多次，需用循环计数而非简单布尔判断。
输入数据含负权重或负价值时，标准DP会崩
所有上述代码都默认重量和价值非负。一旦出现负重量（比如某种“反向占用空间”的道具），或负价值（比如带惩罚的任务），dp[j - w] 下标可能越界，且最大值定义失效——此时不能再用常规背包DP，得转为其他模型（如转化为图上的最长路、或加偏移量做坐标平移）。
实际项目中更常见的问题是：重量或价值过大导致 int 溢出，尤其是价值累加后超 INT_MAX。解决方案包括：
- 用
long long存 DP 值（但注意空间翻倍） - 若只关心是否可达（而非最大价值），改用
bool dp[W+1]做可行性判断 - 对价值极大但数量少的情况，可交换状态定义：以价值为维度，求最小重量
别在没校验输入范围时，就直接套用模板代码跑真实数据。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
