今日刷题量：2
当前刷题总量：136
Easy: 59
Mid: 70
Hard: 7
Day35
常用思想
01背包问题的思想
1.01背包问题的特征：
- 有没有一堆“物品”：n 个元素 / 数字 / 物品。
- 每个东西只能用 0 或 1 次（选 or 不选）。
- 有一个“容量/限制”：
- 比如总重量 ≤ W
- 总时间 ≤ T
- 总花费 ≤ C
- 或者总和要恰好等于 target（子集和）
- 问题目标通常是：
- 能否达到某个和（bool）
- 最大值是多少（max）
- 有几种方法（count）
- 满足这几个特征，大概率就是 01 背包
2.统一抽象成“物品 + 容量
- 第 i 个物品：
- weight[i]（体积/重量/时间/花费……）
- value[i]（价值/得分/收益……）
- 背包容量：W（上限）
- 然后问题就变成：在容量不超过 W 的前提下，选一些物品，让某个指标最优 / 是否可行
3.DP 的三大核心：状态、转移、初始化
1.状态定义：
二维状态：：dp[i][j] = 考虑前 i 个物品，容量为 j 时能得到的最大价值
一维滚动数组：：dp[j] = 在容量为 j 时，能得到的最大价值
2. 转移方程（01 背包核心）
对于第 i 个物品，重量 w = weight[i]，价值 v = value[i]：
- 不选：继承之前的状态
- 选：加上当前物品的贡献
二维：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);
一维：（注意是 dp[j - w]）：dp[j] = max(dp[j], dp[j-w] + v);
3. 初始化
（1）最大价值型：dp[0] = 0
其他初始化为“无效值”（比如 -INF）或 0，取决于题目是否允许“什么都不选”。
（2）可行性型（子集和 / LeetCode 416）
dp[0] = true：容量为 0 时，“不选任何物品”天然可行
其他 dp[j] = false
4、一维滚动的关键：内层循环必须倒序
- 为什么要倒序？
- 因为希望 dp[j-w] 是“上一轮（不含当前物品）”的值。
- 如果从小到大更新：
- dp[j-w] 可能已经被当前物品更新过，相当于允许一个物品使用多次 → 变成完全背包了。
- 倒序可以保证：在当前物品这一轮中，每个 dp[j-w] 都还是上一轮的旧值。
- 因此：
- 01 背包 + 一维 dp → 内层 j 必须从大到小遍历。
一维写法时，一般这样写：
点击查看代码
for (int i = 0; i < n; ++i) {int w = weight[i], v = value[i];for (int j = W; j >= w; --j) { // 一定是从大到小dp[j] = max(dp[j], dp[j-w] + v);}
}练习题目
46.携带研究材料（mid）：https://kamacoder.com/problempage.php?pid=1046
416.分割等和子集（mid）：https://leetcode.cn/problems/partition-equal-subset-sum/description/