1. 从线性DP走到背包：这天的学习坐标
如果你也在跟着某个算法训练营的节奏走，大概率会有这种感觉：前面几天的动态规划还算温柔，什么爬楼梯、打家劫舍、最长递增子序列，状态转移方程就一两行，照着模板套也能写出来。但到了Day36这个节点，画风突然就变了。动态规划part05，正式进入背包问题，而且是那种"会了就会一片，不会就只能干瞪眼"的经典模型。这一天学的东西，基本把后续所有背包变体、甚至面试里很多中等偏上的DP题目都串起来了。
先说清楚这天在训练营整个DP体系里处于什么位置。一般课程会把动态规划拆成三块走：第一块是线性DP，一维状态就能搞定，重点是找出"当前这步依赖前一步的哪个值"；第二块就是背包问题，从01背包开始，到完全背包、多重背包、分组背包，核心变化在于"同一件物品能用几次"和"物品之间的依赖关系"；第三块才是区间DP、树形DP、状压DP这些更复杂的场景。
Day36属于第二块的起点，也是最关键的一天。因为后面所有背包模型，90%的思维都是从01背包延伸出去的。这天要是没吃透，后面完全背包的排列组合问题、分组背包的层序遍历写法，甚至「目标和要求」之类的题目，都会卡得很难受。
训练营里的推进方式一般也比较生猛：先花一个课时把01背包的二维DP讲明白，然后立刻上滚动数组和一维优化，接着就扔一堆变体题让你刷。很多人在这一天掉队，不是听不懂，而是题目换个马甲就认不出来了。比如把一个数组劈成两半，问能不能凑出相等的和，这题表面跟背包毫无关系，实际是判断某个容量能不能恰好装满。这类思维切换，就是part05真正要练的东西。
所以这篇文章我不打算复述PPT上的公式推导，而是把这一天的学习路径、每一步背后的"为什么"、以及我实际做题时踩过的那些坑，完整拆给你看。无论你是自己刷题还是跟着训练营，这条链路走通了，DP就算真正入门了。
2. 01背包的状态定义：为什么非要多开一维
2.1 从暴力枚举到DP的思维跨越
先看最基础的题目模型：有N件物品，每件有重量w[i]和价值v[i]，你有一个容量为C的背包，问最多能装下多少价值。
暴力做法是什么？每件物品选或不选，一共2^N种组合，N稍微一大就完蛋。那么怎么用DP救场呢？关键在于找到一个递推结构：当我处理到第i件物品时，我只需要知道"之前i-1件物品在某个容量下能装出的最大价值"，而不需要知道具体选了哪几件。这个"把集合划分成子集，只保留每个子集的最优值"的思路，就是DP压缩状态的根本原因。
于是状态定义就顺理成章了：dp[i][j]表示"从前i件物品中选，总重量不超过j的前提下，能获得的最大价值"。注意这里有两个维度：一个是"处理到第几件"，一个是"当前背包容量的限制"。两个维度缺一不可，因为你要同时记录"已经考虑过哪些物品"和"当前还有多少空间"。这就是为什么01背包第一版是二维DP——状态必须完整，才能保证每一步的转移是局部最优且不漏解。
2.2 转移方程的完整推导
对于第i件物品，只有两种决策：不拿，或者拿。
如果不拿第i件，那么dp[i][j] = dp[i-1][j]，这最简单，就是继承前i-1件物品在容量j下的结果。
如果要拿第i件，前提是容量j至少能放得下w[i]，即容量j大于等于w[i]。拿完之后，背包剩余容量是j - w[i]，那么前面i-1件物品就得在容量j - w[i]下决策，也就是dp[i-1][j - w[i]]。再加上第i件物品的价值v[i]，所以dp[i][j] = dp[i-1][j - w[i]] + v[i]。
两者取最大，得到完整方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])，其中j >= w[i]；否则dp[i][j] = dp[i-1][j]。
很多初学者写代码时会纠结边界条件：i从1开始，j从0到C遍历，dp[0][j]全部初始化为0，表示"一件物品都没选时价值为0"。这个初始化必须写在循环之前，否则第一行物品的状态转移会读取到未定义的值。
2.3 两层循环的先后顺序到底有没有讲究
二维版本里，外层循环物品i、内层循环容量j，还是反过来，其实都能算出正确答案。因为二维dp[i][j]依赖的是dp[i-1][...]，只要在计算第i层时i-1层已经算完，行列顺序不影响正确性。
但说句实话，我建议你从第一天起就统一习惯"外层物品、内层容量"的写法。因为等到下一节学一维优化的完全背包时，循环顺序直接决定了是组合数还是排列数，这是完全背包最容易错的点。习惯一旦建立，后面分清先遍历物品还是先遍历背包就会容易很多。
训练营里还有一个通用问法：能不能把容量那层循环改成从大往小遍历？二维版本里从C到0也不行，从0到C也行，答案不变。但这个小问题其实是在为一维倒序优化埋伏笔。你先记住"二维无所谓"，后面优化就有对比了。
3. 空间优化：滚动数组和一维倒序到底在干什么
3.1 滚动数组：省一个维度但不改变思维
二维dp的空间是(N+1) x (C+1)，N和C一旦到几千，内存就上去了。第一个优化思路是滚动数组。因为dp[i][...]只依赖dp[i-1][...]，那么我只需要两个数组：pre[j]存上一行结果，cur[j]存当前行结果。每次遍历完第i行，把cur整体复制到pre即可。空间从O(NC)降到O(C)。
这个写法的好处是思维负担小，几乎没有改方程，只是把dp[i-1]换成pre、dp[i]换成cur。坏处是每次还要memcpy，时间上有一点浪费，刷题时也显得不够优雅。训练营里一般会把它当作过渡，很快就会教一维写法。但从学习曲线角度，滚动数组值得亲手写一遍。它能帮你建立"状态只依赖上一层"的直觉，后面学树形DP时，这个直觉会反复用到。
3.2 一维数组：为什么必须是倒序
滚动数组的进一步压缩，是直接用一维数组dp[j]来表示"当前物品处理完、容量为j时的最大价值"。转移方程变成了：
dp[j] = max(dp[j], dp[j - w[i]] + v[i])
这里的关键问题是：容量j必须从大到小遍历，即j从C向下循环到w[i]。
为什么？因为一维数组dp[j - w[i]]如果从前往后遍历，会被当前这一轮循环覆盖掉，读到的是"已经决定拿第i件物品之后的值"，而不是上一轮（即前i-1件物品）的值。这样一来，一件物品就可能被多次使用，01背包直接退化成了完全背包。倒序遍历则保证dp[j - w[i]]还没被本轮更新，每次用的都是上一层的数据。
我用一个生活类比讲给朋友听：假设你有一张抄满各种价签的旧账单，你从后往前改，改后面的数字不会影响你前面还没改的数字。但如果从前往后改，你后面要用到前面数字时，它已经变成了改动后的新数字。
3.3 一维优化后，初始化还是一样吗
空间优化后，维度没了，但状态语义没变：dp[j]仍然表示"容量为j时能获得的最大价值"。所有dp[j]在起始时都初始化为0，因为在没有任何物品时，任何容量下的最大价值都是0。这个初始化方式适用于绝大多数求最大价值的背包题。
不过要注意，如果题目要求"恰好装满背包"，初始化就要变成：dp[0] = 0，dp[1...C] = -INF（一个极大负数）。为什么？因为"恰好装满"要求dp[j]只能由"可以精确凑成j的组合"转移来，那些凑不满的容量应该表示成负无穷，让max运算自动丢弃。如果不这样处理，dp[j]一直为0，所有凑不满的情况也会被当成合法答案。这个细节在「分割等和子集」这类题里是命门。
训练营里有个不成文的检查习惯：写完一维循环后，先把j的遍历顺序圈出来，是倒序说明是01背包，是正序就在脑子里立刻标记"这里可能有问题"。这个习惯帮我省了很多debug时间。
4. 01背包的经典变体：披着不同外衣的同一副骨架
4.1 分割等和子集：从数组问题到背包问题的翻译
LeetCode 416的「分割等和子集」，题目说给一个数组，问能否分成两个和相等的子集。很多新手第一反应是排序+双指针，但这种情况有反例。正确思路其实很短：数组总和为sum，如果sum是奇数，直接返回false；如果是偶数，问题就变成"能否从数组中选出若干个数，使它们的和恰好等于sum/2"。
这不就是"恰好装满"版的01背包吗？物品的重量和价值都是同一个数，背包容量是sum/2，问dp[sum/2]能否等于sum/2。当我们把初始化改成dp[0]=0、其他为-INF的时候，就能精确判断：只要dp[target] != -INF，说明可以凑出来。
这个变体题的重要价值在于它逼你识别"重量和价值重合"的场景。以后很多题目里，数组元素既当重量又当价值，这种抽象能力是part05的核心考核点。
4.2 最后一块石头的重量：反过来包装的最大价值问题
「最后一块石头的重量 II」也是同一副骨架。题目里的操作描述一大堆，但本质是：把石头分成两堆，让两堆总重量之差最小。由于总重量固定，最小差值等于让其中一堆尽可能接近总重量的一半。这依然是一个容量为sum/2的01背包，目标是最大化这一堆的总重量。算出能凑出的最大重量x之后，答案是(sum - x) - x，也就是2*(sum/2 - x)的绝对值。
这类题考察的是"从问题描述里剥离出背包模型"的能力。题目没有直接说"选若干物品放入容量固定背包"，而是用"相撞、抵消、差最小"这些词语做包装。我在训练营里看过太多人卡在理解题意上，一旦想通，代码二十分钟就能写出来。
4.3 目标和：为什么可以加负数？拆成两个子集就好
「目标和」让你给每个数前面加正号或负号，使总和等于target。这里的转化也很经典：设所有正号数字之和为P，那么负号部分总和就是sum - P，于是P - (sum - P) = target，得到P = (sum + target) / 2。所以问题变成"选若干个数，使它们加起来正好等于P"。同样，sum + target必须是非负偶数，否则无解。
注意这个变体的目标变成了求"方案数"，而不是最大价值。dp[j]定义就成了"凑出容量j的方案数量"，转移方程也变成了dp[j] += dp[j - w[i]]（注意是累加，不是取max）。训练营里讲到这个题，会专门强调：同样是01背包，求最值、求可行性、求方案数，三者的转移差异只在最后一步。这个"一鱼三吃"的概念如果没理解，后面的完全背包方案数问题也会错。
4.4 一和零：二维约束的入门
当题目里每个物品同时消耗两种资源（比如0的个数和1的个数），状态自然就要增加一维。LeetCode 474的「一和零」，每个字符串有m个0和n个1，问你最多能取多少个字符串，让0的个数不超过m、1的个数不超过n。
这题的dp就是一个三维朴素、二维优化的过程：dp[i][j]表示"使用i个0、j个1时能拿到的最大字符串数量"。每个字符串遍历一次，内层两个容量维度都从大到小倒序。写了这道题，你对"约束每多一个维度，就在dp上多开一维"的理解就会固化。后面像多重背包的二进制优化，本质也是在不同维度上做文章。
5. 完全背包与01背包的关键差异：正序、重复选择、组合与排列
5.1 完全背包的转移方程与一维正序问题
进入part05的后半段，训练营一般会立刻引入完全背包：每件物品可以无限多次选取。很多人以为只是把01背包的循环方向从倒序改成顺序，这话一半对，但只理解了皮毛。
完全背包的一维转移方程是同一个：
dp[j] = max(dp[j], dp[j - w[i]] + v[i])
但此时j的遍历方向必须是正序，即从w[i]到C。为什么？因为当j从小往大更新时，dp[j - w[i]]已经被当前这一轮更新过了，这个值本身就包含了"刚刚又选了一次第i件物品"的结果。于是dp[j]在更新时，会基于dp[j - w[i]]再次加上v[i]，相当于允许同一件物品被反复取用。这正好是"无限次使用"的定义。
这个差异，是背包系列里最容易出事故的地方。我有一次写完全背包求方案数，忘了把j方向从C到w[i]改成w[i]到C，结果答案比标准值小了很多，查了半小时才发现。之后我给自己立了个规矩：每次写完循环，第一行看方向，第二行看初始化，两个都没问题再看转移。
5.2 组合问题与排列问题：遍历顺序决定一切
完全背包里还有一个让无数人崩溃的细分：当题目问"凑成某个容量有几种方案"时，先遍历物品和先遍历容量会得到完全不同的结果。
先遍历物品再遍历容量，得到的是组合数：不会重复记录{1,2}和{2,1}这种顺序不同的排列，因为每个物品只在固定的外层次序中出现。先遍历容量再遍历物品，得到的是排列数：它在每个容量下都会把所有物品重新枚举一遍，自然会覆盖所有顺序。典型例子是LeetCode 377「组合总和IV」求排列数，就必须外层背包容量、内层物品；而LeetCode 518「零钱兑换II」求组合数，就必须外层物品、内层容量。两者题目描述几乎一样，解法就错在一个循环顺序上。
训练营老师讲到这里，通常会让大家把两个题放一起对比着做，我也推荐你照样操作。光记结论容易忘，亲手把两种遍历方式的dp表打出来看一眼，就知道为什么一个是组合一个是排列了。
5.3 完全背包的实战题目联动
Day36这天我实际刷的题里，比较有代表性的三题是：「零钱兑换」（求最少硬币数）、「零钱兑换II」（求组合方案数）和「完全平方数」。这三题按顺序做下来的体验是：
- 「零钱兑换」求最少数量，初始化dp[0]=0、其他为INF，转移用min。这题提醒你：不是所有背包问题都用max。
- 「零钱兑换II」求方案数，转移用+=。这题提醒你：组合方案数怎么避掉重复。
- 「完全平方数」属于自己给自己造物品，把每个平方数当成一件物品，然后跑完全背包。
三题做完，你就会发现完全背包不是一种新算法，而是"把01背包的一件物品循环扩大到多件物品串联使用"的写法变体。训练营的part05如果只掌握到这里，其实已经胜过很多只背模板的刷题党了。
6. 初始化与状态语义：dp[0]=0背后藏着三种答案
6.1 三种初始化的用法对照
很多初学者觉得初始化没什么了不起，无非是memset成0。但在背包问题里，初始化几乎等于定义了"什么才算合法答案"。我把三种常见情况列在下面，方便你直接对照着记：
| 问题类型 | dp初始化 | 转移后得到的结果 |
|---|---|---|
| 求最大价值（不要求恰好装满） | dp[0...C]全为0 | dp[j]表示容量不超过j时的最大价值 |
| 求最大价值（要求恰好装满） | dp[0]=0，dp[1...C]=-INF | 只有能恰好凑满的状态才是正数，其他保持无意义负值 |
| 求方案数 / 最少数量 | dp[0]=1（或0），其他参考题设 | dp[j]表示精确凑成j的方案数或最少数量 |
表格里最值得琢磨的是"求方案数"的初始化：dp[0]=1在语义上表示"凑出0的方式有一种，也就是什么都不选"。这个约定看似微不足道，但如果没有它，所有累加转移都会从源头上断了。
6.2 一个必须做的小实验：打印dp表
训练营里我最推崇的一个动作，是在笔记本上把前几行dp表手工打印出来，看看每次更新后哪些格子变了、方向是什么。比如01背包，用物品(2,3)、(3,4)、(4,5)跑一遍容量为6的表，你会在纸上清楚看到：倒序遍历让每个物品最多被用一次，而正序遍历会让格子像波浪一样反复叠加。
现在很多在线IDE也能单步调试，但我更推荐手写表格一次。原因很简单：手写表格时你会被迫关注每个格子的来源，而不是只盯着代码跑没跑通。当你亲手在纸上填出"当前行当前列究竟引用的是上一行哪个格子"时，滚动数组和一维倒序的机理就不再是死记硬背了。这个动作花不了二十分钟，但效果比看十遍题解都强。
7. 针对Day36的刷题路线与踩坑总结
7.1 一个可复制的刷题顺序
如果你今天正好学到part05，我推荐你按这个顺序刷，不要东一榔头西一棒槌：
- 先写纯01背包模板题：AcWing 2「01背包问题」，或者洛谷P1048「采药」，目标是能默写出一维倒序AC。
- 再做无法一眼识别的01背包变体：LeetCode 416「分割等和子集」、LeetCode 1049「最后一块石头的重量II」。
- 接着上求方案数的：LeetCode 494「目标和」。
- 然后切换到完全背包：LeetCode 518「零钱兑换II」和LeetCode 377「组合总和IV」对比做。
- 最后做二维约束的LeetCode 474「一和零」收尾，感受状态维度扩展。
这套路线的好处是层层递进，每一步都在给下一步铺路。比如先做416再做494，你对"恰好装满"的理解会瞬间加深；先做518再做377，你对组合与排列的区别会彻底建立。
7.2 我在part05踩过的三个坑
第一个坑是数组越界。物品重量可能大于背包容量，所以内层循环的起点要写成max(w[i], j)这种形式，或者直接判断j >= w[i]。别小看这个问题，有些题目数据很温和，本地测试没问题，提交就RE，大概率就是这里。
第二个坑是初始化遗忘。做「目标和」时我一开始dp[0]忘了设成1，结果所有方案数都算成0。这种错误编译器不会报错，只能靠对语义的理解去检查。我后来养成的习惯是每次定义dp之后，先在注释里写一行"dp[0]的含义是什么"，写不清楚就停下来重想。
第三个坑是复制01背包代码改完全背包，只把j的方向改了，却忘了有些题根本不适合一维直接套。比如分组背包、多重背包带数量限制时，完全背包的正序逻辑会出大问题。part05阶段你还没碰到分组背包，但学到这里就要有"背包框架不是万能钥匙"的意识，等后面学了更复杂的模型，才不会一脸懵。
7.3 学完这一天的检验标准
怎么判断自己是不是真的学明白了Day36？我比较喜欢用四条标准来自测：
- 能不能不用翻笔记，在五分钟内写出01背包的一维倒序模板，并解释为什么倒序。
- 能不能用自己的话讲清楚"恰好装满"和"不超过容量"两种初始化差异。
- 能不能把「分割等和子集」「最后一块石头的重量II」「目标和」三题归到一个模型下，说出它们的差异只有求值方式。
- 能不能在完全背包里，通过切换物品和容量的遍历顺序，主动控制结果是组合方案数还是排列方案数。
四条全过，你今天这一课就值回票价了。如果还差一些，也不用急，把上面的表格和实验复习一遍，再刷两三个变体题，这一关很快就跨过去了。
