01背包需倒序遍历容量j以确保每物只选一次，状态转移为dp[j]=max(dp[j],dp[j−w[i]]+v[i])；完全背包则正序遍历，允许重复选取。
01背包：状态转移写错就全错
核心是 dp[j] = max(dp[j], dp[j - w[i]] + v[i])，且必须倒序遍历容量 j。正序会重复选同一物品，变成完全背包行为。
常见错误现象：dp[10] 算出来比手算大很多，或者小数据对、大数据错——大概率是循环方向反了。
- 倒序从
W到w[i]（含），保证每个物品只用一次 -
dp数组大小至少为W + 1，下标0表示容量为 0 的最大价值 - 初始化全为
0即可（求最大价值，非恰好装满）；若要求“恰好装满”，除dp[0] = 0外其余设为负无穷
完全背包：顺序遍历才是关键
状态转移式看起来一样：dp[j] = max(dp[j], dp[j - w[i]] + v[i])，但内层循环必须正序，让已更新的 dp[j - w[i]] 参与后续计算，从而允许重复使用当前物品。
使用场景：硬币找零（最少硬币数）、无限供应的物品组合优化。
立即学习“C++免费学习笔记（深入）”；
- 正序从
w[i]到W，每轮都复用本物品的更新结果 - 如果想压空间又不想混淆，建议先写二维版
dp[i][j]理清逻辑，再滚动优化 - 注意：和 01 背包共用同一份代码却只改循环方向，极易漏掉边界检查（比如
j - w[i] 时跳过）
初始化与边界：不是所有题都从 0 开始
很多题不满足“容量为 0 时价值为 0”这个默认假设。比如要求“总重量恰好等于 W”，那 dp[0] = 0 是对的，但 dp[1..W] 初始值不能是 0，否则会误把未达成的状态当有效解。
- 恰好装满类问题：用
INT_MIN或一个极小负数初始化dp[1..W]，避免无效状态参与转移 - 最大价值类问题（不要求装满）：全初始化为
0即可 - C++ 中
vector<int>(W + 1, 0)</int>和vector<int>(W + 1, INT_MIN)</int>差异直接影响答案正确性
空间优化后调试困难？加个打印点就行
一维 dp 数组省空间，但失去中间过程，出错时很难定位哪一轮、哪个物品搞错了。别硬扛，临时加一行输出就能省半天。
- 在每次外层循环（即处理第
i个物品）结束后，打印前几个dp值：cout - 对比手算的小样例（比如 2 个物品、容量 5），一眼看出哪次更新异常
- 上线前删掉即可，不影响逻辑——这比翻十遍状态转移方程快得多
真正卡住的往往不是 DP 思路，而是初始化含义没吃透，或循环方向和依赖关系对不上。多打一行日志，比重写三遍更可靠。
