0-1背包状态dpi表示前i个物品容量j的最大价值，转移为max(dpi-1, dpi-1]+v[i])；完全背包因可重复选，转移为max(dpi-1, dpi]+v[i])，需正序遍历。
动态规划解决背包问题，核心在于状态定义清晰、转移逻辑自然、实现方式贴合约束。不是套模板，而是理解“选或不选”这件事怎么在表格里一步步算出来。
0-1背包问题的状态定义与转移
状态 dp[i][j] 表示：考虑前 i 个物品，背包容量为 j 时能获得的最大价值。
这个定义直接对应问题目标——既要限制物品数量（前 i 个），又要控制空间（容量 j）。
转移只依赖两种决策：
- 不选第
i个物品 → 价值就是dp[i-1][j] - 选第
i个物品 → 前提是j ≥ weight[i]，此时价值为dp[i-1][j - weight[i]] + value[i]
所以状态转移方程是：
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])
注意边界：当 j 时，第二项无效，只能取第一项。
完全背包问题的关键区别
每个物品可重复使用，状态定义仍是 dp[i][j]（前 i 种物品，容量 j 的最大价值），但转移逻辑变了：
- 不选第
i种 →dp[i-1][j] - 选第
i种（至少一次）→dp[i][j - w[i]] + v[i]（注意这里是i而非i-1，表示已选过该物品，还能再选）
方程变为：
dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + v[i])
实现时，内层循环正序遍历容量（j 从 w[i] 到 W），才能复用当前轮更新过的值。
空间优化的实质
二维表中，dp[i][j] 只依赖上一行（i-1）和当前行左侧（i 行更小容量）。
因此可用一维数组滚动更新：
- 0-1背包：内层
j逆序遍历（避免刚更新的dp[j-w]被重复使用） - 完全背包：内层
j正序遍历（允许同一物品多次贡献）
例如 0-1 背包的一维写法：
for (int i = 0; i = w[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
}
}
初始化与边界处理
-
dp[0][j] = 0：没物品可选，价值必为 0 - 若题目要求“恰好装满”，则除
dp[0][0] = 0外，其余dp[0][j]设为负无穷（或非法标记），避免用无效状态参与转移 - 实际编码中常用
-1或极小值标记非法状态，更新时跳过
不复杂但容易忽略
