1. 先搞清楚题目在问什么：01背包方案数的识别信号
很多同学一看到"方案数"三个字，第一反应是套组合数公式，第二反应是DFS枚举。这两种反应本身没问题，但放到GESP六级的赛题里，大概率会超时。为什么？因为01背包求方案数的题目，题干往往长得非常像"01背包求最大价值"的模板题，只不过最后一句问法变了，很多考生根本没意识到这两者在算法上完全是两条路。
我见过的GESP六级真题和模拟题里，这类题的典型问法有几种：
- "恰好装满容量为V的背包，一共有多少种不同的装法？"
- "在总重量不超过C的前提下，有多少种方案？"
- "背包恰好装满时，最大价值对应的方案数是多少？"
注意，第三种问法最阴险，它把"求价值"和"求方案数"揉在一起考，如果只会背模板，看到这题直接懵。判题的时候，很多人能算出最大价值，却算不出"在最大价值的前提下到底有几种组合方式"。
先说识别信号。只要题干里出现"多少种""方案数""组合方式""搭配方法"这类词，同时物品有重量且每个物品最多用一次，那基本就是01背包求方案数没跑了。如果物品可以重复使用，那是完全背包求方案数，虽然转移方程长得像，但内层循环的方向完全相反，后面我会专门说。
再有一个隐藏信号：题目里如果还带着"价值"这个维度，比如"在重量不超过C的情况下能获得的最大价值，以及达到该最大价值的方案数"，那就要警觉。这类题要求你的状态不仅要记录最大值，还要记录最大值对应的方案数，属于"双维度DP"，比纯方案数多一层逻辑。很多人栽就栽在只维护了价值，没维护方案数，或者维护方案数时没考虑"并列最大"的情况。
顺便说一句，GESP六级对动态规划的考法，基本不会出那种一眼就能看出是DP的题。它喜欢场景化包装，比如"有N种面值的邮票，每种只能用一张，问能凑出多少种不同的邮资"，或者"有若干根长度不同的木棍，从中选几根拼成指定长度，问有几种拼接方式"。这些全是01背包方案数套了个生活场景的皮。识别本质，比背代码重要得多。
这里先给结论：01背包求方案数的核心代码极短，短到让你怀疑它的含金量，但它背后的状态定义、初始化逻辑和循环顺序，每一项都有讲究，少一个条件答案就错。
2. 状态设计：从"选最大值"到"数方案"的思维转换
2.1 经典01背包的状态，先复习一遍
经典的01背包求最大价值，状态是这样定义的：
dp[j] 表示容量为j的背包能装下的最大价值转移方程：
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);意思是，对于第i个物品，要么不装（保持原状），要么装（腾出w[i]的空间，加上v[i]的价值），两者取大。
但求方案数的时候，如果你还按"取大"的思路想，就掉进坑里了。为什么？因为"方案数"这个量，根本不能用max来聚合。
举个例子。容量是5，有个物品重量是3。如果最大价值是10，那这个10对应的装法可能是"A方式"，也可能是"B方式"。你要问的是"有几种方式能拿到10分"，而不是"10分够不够大"。所以方案数必须用加法来聚合。
2.2 方案数DP的状态定义
求方案数，状态定义有两种写法，我都说一下。
第一种，也是最常见的一种，状态直接就是方案数本身：
dp[j] 表示容量为j的背包，恰好装满（或不超过容量）时的方案总数转移方程：
dp[j] = dp[j] + dp[j - w[i]];这个式子的含义是：当前容量j的方案数 = 不装第i个物品时已有的方案数（dp[j]）+ 装入第i个物品后，剩余容量j-w[i]对应的方案数（dp[j-w[i]]）。这个"加法"非常好理解，但细节在于dp[j-w[i]]里存的到底是什么语义，这直接跟初始化挂钩。
第二种，是"价值+方案数"双维度写法。这种适用于题目既要最大价值，又要方案数的场景，一般用结构体或两个数组配合：
struct Node { int value; // 当前容量下的最大价值 long long count; // 达到该最大价值的方案数 };或者分开两个数组：
int val[V]; // val[j] 表示容量j的最大价值 long long cnt[V]; // cnt[j] 表示容量j且价值为val[j]时的方案数转移时不能只简单加减，要分类讨论：
- 如果 val[j] < val[j-w[i]] + v[i]，说明装了第i个物品更优，那么 val[j] 更新为新的最大值，cnt[j] = cnt[j-w[i]]；
- 如果 val[j] == val[j-w[i]] + v[i]，说明两种装法价值一样，那么 cnt[j] = cnt[j] + cnt[j-w[i]]（方案数相加）；
- 如果 val[j] > val[j-w[i]] + v[i]，什么都不做。
你会发现，第二种写法里的"加法"是有前提的：只有在价值相等时才相加，价值不相等时方案数不能简单相加。这就是"并列最优"的处理逻辑，很多同学的代码错就错在这里，不加判断直接加，把不优的方案也算进去了。
2.3 为什么方案数DP不能用max
我用生活化的例子解释一下。假设你手里有1张100元、2张50元，你觉得"我有3张钱"，这是数的张数，不是数的金额。方案数的本质是"有多少种达成方式"，它的聚合规则天然是加法。而最大值是"哪一个更大"，聚合规则是max。两者完全不同。
再往深一层，方案数DP其实是在做"计数问题"，它背后是组合计数的乘法原理和加法原理。一个物品选或不选，是两条互斥的路径，那么总方案数就是两条路径的方案数之和。这也是为什么转移方程里是 dp[j] + dp[j-w[i]] 而不是 max。把这条思维理顺了，再遇到什么"爬楼梯方案数""凑零钱方案数"都是一回事。
3. 核心代码拆解：一维滚动数组的正确打开方式
3.1 二维递推，先把逻辑跑通
不急着上优化，先用二维数组把逻辑完整推导一遍。定义：
dp[i][j] 表示前i个物品中挑选若干件，恰好装满容量为j的背包的方案数。初始：dp[0][0] = 1，表示0个物品凑出0容量，有一种方案（啥也不选）。 其他 dp[0][j] (j>0) = 0，表示0个物品没有办法凑出正数容量。
第i个物品，重量 w[i]：
- 不选它：方案数是 dp[i-1][j]；
- 选它（前提是 j >= w[i]）：方案数是 dp[i-1][j-w[i]]；
- 总方案数等于两者之和。
所以递推式：
dp[i][j] = dp[i-1][j]; if (j >= w[i]) dp[i][j] += dp[i-1][j-w[i]];我拿一个具体例子手算一遍，你就能直观看到这个过程。假设背包容量 W=5，有3个物品，重量分别是 2、3、5（暂时不管价值，因为纯方案数题不需要价值）。
初始状态，只考虑前0个物品：
- dp[0] = [1, 0, 0, 0, 0, 0]，下标0到5。
处理第1个物品，重量2：
- 不选：dp[1][j] 继承 dp[0][j]；
- 选：dp[1][2] += dp[0][0]，即 dp[1][2] = 0 + 1 = 1。
- 所以 dp[1] = [1, 0, 1, 0, 0, 0]。
处理第2个物品，重量3：
- 继承：dp[2][j] = dp[1][j]；
- 选：dp[2][3] += dp[1][0] = 1；dp[2][5] += dp[1][2] = 1。
- 所以 dp[2] = [1, 0, 1, 1, 0, 1]。含义是：容量3有1种（单独物品3），容量5有1种（物品2+物品3）。
处理第3个物品，重量5：
- 继承：dp[3][j] = dp[2][j]；
- 选：dp[3][5] += dp[2][0] = 1。
- 所以 dp[3][5] = dp[2][5] + 1 = 2。
最终 dp[5] = 2，对应两种方案：物品2+物品3，或者单独物品5。这个手算结果可以用来验证你写的代码对不对，非常实用。
3.2 压缩成一维，关键在循环方向
二维写法用来理解，一维写法用来过题。一维滚动数组的代码是这样的：
#include <bits/stdc++.h> using namespace std; const int MAXV = 10005; long long dp[MAXV]; int main() { int n, W; cin >> n >> W; int w[105]; for (int i = 1; i <= n; i++) { cin >> w[i]; } // 初始化灵魂 dp[0] = 1; // 其余 dp[j] 保持为 0 for (int i = 1; i <= n; i++) { // 01背包：内层必须倒序遍历 for (int j = W; j >= w[i]; j--) { dp[j] = dp[j] + dp[j - w[i]]; } } cout << dp[W] << endl; return 0; }这段代码只有十几行，但里面有两个最容易写错的地方。
第一，内层循环必须从 W 倒着到 w[i]。原因和经典01背包一样：如果正序遍历，dp[j-w[i]] 可能已经在当前物品这一轮被更新过，相当于第i个物品被重复使用了，这就从"01背包"变成了"完全背包"。在方案数问题上，这个错误更隐蔽，因为结果看起来也有意义，但不满足"每个物品最多用一次"的约束。我见过有同学正着写样例也能过，一上大测试点就偏，排查半天发现是没倒序。
第二，dp[0] = 1，其他是0。这个初始化到底为什么是灵魂，我们下一节专门讲。这里先提醒一句，千万别以为是"dp[0] = 0"，也别以为所有dp[j]初始都应该是1。初始化错了，方案数直接翻倍。
3.3 复杂度分析
01背包方案数的时间复杂度是O(n * W)，空间复杂度优化后是O(W)。n是物品数，W是背包容量。GESP六级的数据范围，物品数一般不超过100，容量一般在1000到10000之间，这个复杂度在1秒时限内绰绰有余。
方案数很容易超过int范围。举例来说，100个物品每个重量都是1，背包容量是50，方案数是C(100, 50)，这个数远超int上限。所以建议直接用 long long 存。如果题目明确要求对某个大质数取模，那就模运算处理，下面会有代码。
4. 初始化细节：dp[0] = 1是灵魂，不容商量
4.1 两种题型，两种初始化
初始化不是玄学，它决定"不可达状态"怎么表达。
第一种题型："恰好装满"。这时候 dp[0] = 1，其余 dp[j] = 0。含义是：容量为0时，有一种方案（什么都不选），容量大于0但还没开始装物品时，任何正容量都无法达到，所以方案数为0。递推过程中，只有真正能凑到的容量才会被逐步"点亮"，凑不到的保持0。
第二种题型："不超过容量C"。这时候就微妙了。如果你只想求"容量不超过C的所有方案总数"，需要把问题转换一下，或者把小于等于C的所有dp[j]加起来。但更常见的写法是，仍然采用"恰好装满"的思路，最后累加：
long long ans = 0; for (int j = 0; j <= C; j++) ans += dp[j];为什么？因为"不超过容量C"的方案，其实际占用容量可能是0,1,2,...,C中的任意一个值，把这些恰好装满的方案数全部求和，就是"不超过"的方案数。很多题目答案要求输出这个累加值，如果直接输出dp[C]会漏掉很多，这是高频错误点。
这里有个容易绕进去的弯：如果把初始化改成所有dp[j] = 1，含义就变成了"任意容量都自带一种方案"，那显然不对，因为它会把"凑出该容量"和"什么都没做"混为一谈。所以一律以 dp[0] = 1、其余为0作为起点，然后根据题目问法决定最后是输出dp[W]还是求和。
4.2 再说说"恰好装满"和"不超过容量"的场景差异
GESP六级更爱考"恰好装满"。为什么？因为它能考察考生对状态语义的理解。比如"有N种重量的砝码，每种只有一个，问能称出多少种不同的重量"，这是一个典型的恰好装满问题。每种重量j如果能被凑出，dp[j] > 0；最后统计有多少个j满足dp[j] > 0。
再比如"给定一堆物品和一辆载重为W的车，问有多少种装货方式"，如果车没装满也行，那就是"不超过容量"的累加问题。这两种问法和初始化没有直接关系，真正区别只在最后的答案汇总方式上。但很多同学的思维定式是"求方案数就输出dp[W]",结果遇到"不超过容量"直接丢掉一半方案。
4.3 用一维代码实现"恰好装满"方案数
完整可提交的模板：
#include <bits/stdc++.h> using namespace std; const int MAXV = 10005; long long dp[MAXV]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, W; cin >> n >> W; vector<int> w(n + 1); for (int i = 1; i <= n; i++) { cin >> w[i]; } dp[0] = 1; for (int i = 1; i <= n; i++) { for (int j = W; j >= w[i]; j--) { dp[j] += dp[j - w[i]]; } } cout << dp[W] << endl; return 0; }如果题目要求取模，把 dp 数组初始化和每次加法都取模即可：
const long long MOD = 1000000007; ... dp[j] = (dp[j] + dp[j - w[i]]) % MOD;4.4 初始化的一个冷门坑：用-1初始化不可达状态
有些同学在同时求最大价值和方案数时，为了区分"不可达"和"方案数为0"，会先把 dp[j] 初始化为 -1，逻辑是"-1表示凑不到，0表示能凑到但方案数为0"。这个想法本身没错，但实现的时候很容易忘记在比较时把 -1 的情况特判，导致 -1 + 1 变成 0，把不可达状态误判成可达。
我的建议是：能用 dp[0]=1、其余为0 解决，就不要引入-1。只有当题目同时要求"最大价值"且价值本身可能为0（比如0价值物品）时，才考虑用 -1 区分，并且转移时记得先判断 dp[j - w[i]] != -1。能用简单写法，就别秀复杂写法，比赛里稳才是王道。
5. 变体扩展：GESP六级里常见的进阶考法
5.1 完全背包求方案数：区别只有循环方向
如果物品可以无限次使用，那就是完全背包求方案数。转移方程几乎一样：
dp[j] = dp[j] + dp[j - w[i]];唯一区别：内层循环从 w[i] 正序遍历到 W。
为什么？完全背包允许多次选同一个物品，正序遍历可以让 dp[j-w[i]] 在本轮更新后再参与计算，实现"叠加"效果。我看到的错误里，十有八九是把完全背包的循环方向和01背包搞反。有个很实用的记忆方式：同样是求方案数，01背包倒序，完全背包正序。就这么简单的一个方向，决定了整个题目的对错。
举个经典变体："有若干种面值的硬币，每种数量无限，问凑出总额N有多少种方案"，其实就是完全背包方案数，也叫"换零钱问题"。它的代码和01背包方案数就差一个循环方向。
5.2 最大价值 + 方案数双维度
为了说清楚这个变体，我拿一个具体的题目场景来演示。假设背包容量 W=5，物品重量和价值分别是：(2,3)、(3,4)、(1,2)，求"恰好装满容量5的最大价值，以及达到该最大价值的方案数"。
先手算：可能的装满组合有——
- 物1(2)+物2(3)：总重5，总价7
- 物1(2)+物3(1)+物3(1)？不行，每个物品只能用一次。
- 物2(3)+物3(1)+物3(1)？不行。
- 物2(3)+物1(2)：同上。
- 物3(1)要装满5，得凑5个物3，但物3只有一个。
- 物1(2)+物3(1)只有重量3，填不满。
- 物2(3)+物3(1)重量4，填不满。
所以唯一装满容量5的方案是物1+物2，最大价值7，方案数1。
但如果把物品改成：(1,2)、(2,3)、(3,4)，容量5：
- 组合1：1+2+3，总重6，超了。
- 组合2：1+2，总重3，不行。
- 组合3：1+2+2？不行，物品2只有一个。
- 组合4：2+3，总重5，价值7。
- 组合5：1+1+？不行，物品1只有一个。
- 组合6：1+3，总重4，不行。 结果还是1种。
再设计一个并列最优的例子：(2,5)、(3,5)、(5,10)，背包容量5。重量恰好装满5的组合有：(2+3) 价值10，(5) 价值10。两条路价值并列，都是10。这时候方案数就是2。这类题就是靠"并列最优"拉区分度的。
双维度实现的代码思路如下：
#include <bits/stdc++.h> using namespace std; const int MAXV = 10005; long long val[MAXV]; // 容量j的最大价值 long long cnt[MAXV]; // 容量j达到最大价值的方案数 const long long MOD = 1000000007; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, W; cin >> n >> W; vector<int> w(n + 1), v(n + 1); for (int i = 1; i <= n; i++) cin >> w[i] >> v[i]; cnt[0] = 1; // 容量0，价值0，有一种方案 for (int i = 1; i <= n; i++) { for (int j = W; j >= w[i]; j--) { long long newValue = val[j - w[i]] + v[i]; if (newValue > val[j]) { val[j] = newValue; cnt[j] = cnt[j - w[i]] % MOD; } else if (newValue == val[j]) { cnt[j] = (cnt[j] + cnt[j - w[i]]) % MOD; } } } cout << val[W] << " " << cnt[W] % MOD << endl; return 0; }注意几个细节：当新价值更大时，cnt[j] 直接覆盖成 cnt[j-w[i]]，而不是累加；当价值相等时，cnt[j] 累加。这个逻辑对应了"最大价值变化时方案数重置，最大价值并列时方案数合并"，是整个代码的精髓。
另外这个代码默认了任何容量从0到W都是可达的，但实际中有些容量凑不到，val[j] 会一直是0，cnt[j] 也会是0，不影响结果。如果物品价值可能是0，那就需要把 val 初始化为一个极小值，同时 cnt[0] = 1，才能在严格意义上区分"可达但价值为0"和"不可达"。考场上有时间就处理，没时间就先按上述模板，多数测试点不会卡这个边界。
5.3 二维费用背包方案数
GESP六级偶尔会出现"二维限制"，比如每个物品有重量和体积两种限制，背包有容量和体积两个上限，问方案数。这种题要开二维状态：
dp[j][k] 表示容量为j、体积为k时的方案数转移：
dp[j][k] += dp[j - w[i]][k - c[i]];维度多了一维，复杂度也上来。好在GESP六级对这类题的数据范围都不大，30个物品以内、容量百位级可以接受。
二维费用的关键是初始化仍然是 dp[0][0] = 1，其余为0。循环方向注意两维都要倒序。写起来不难，但要注意数组别越界，内层循环的边界判断要完整。
6. 常见问题与排查技巧实录
6.1 高频Bug速查表
| 错误类型 | 具体表现 | 解决方案 |
|---|---|---|
| 循环方向写反 | 每个物品被重复使用，方案数偏大 | 01背包内层倒序，完全背包内层正序 |
| 初始化错误 | dp[0]设成0，导致所有方案数从源头丢失 | dp[0] = 1，其他为0 |
| 价值方案数并列没判等 | 最大价值并列时方案数漏加 | 转移时分 newValue > val[j] 和 == 两种情况 |
| 没用 long long | 方案数爆int，输出负数或截断 | 全部改成 long long |
| 输出dp[W]但题目要"不超过容量" | 漏算容量不满的方案 | 累加所有 dp[0] 到 dp[W] |
| 用DFS枚举替代DP | 物品数稍大就超时 | 识别背包模型，直接用DP |
| 忘记判断 j >= w[i] | 数组越界或负下标 | 内层循环起点定为 w[i] |
以上每一项我都见过真实案例。特别是"输出dp[W]但题目要不超过容量"这个坑，GESP六级的模拟题里出现过，不少考生当场丢分。
6.2 排错实战：一个经典翻车现场
有一次我帮一个学生排查，他写的代码样例能过，但提交到评测系统就WA。我让他打印中间dp数组，发现在处理第2个物品时，容量3的dp值变成了2，而手算是1。仔细一看，他内层循环写的是正序。正序时，处理重量3的物品，dp[3] = dp[3] + dp[0] = 1没问题，但紧接着 j 增大到6时，dp[6] = dp[6] + dp[3]，这个 dp[3] 已经被本轮更新过，导致第2个物品被使用两次。物品数少、容量小时看不出来，容量一大错误就累积。
这个案例告诉我们一个排错思路：先用小数据手算，把每一轮dp数组的期望值列出来，再打印程序里每一轮的dp数组做对比。第一轮不匹配，说明初始化或外层循环有问题；第几轮开始不匹配，说明那一轮的物品处理有问题。这个方法比盯着代码干想有效得多。
还有一个调试技巧：把 dp[j] 的更新打印出来，看看每次是从哪个 dp[j-w[i]] 转移来的。如果是正序导致的重复使用，你会发现 dp[j-w[i]] 出现"本轮已更新的新值"，一抓一个准。
6.3 考场策略：什么时候用二维，什么时候贪省事
我个人的习惯是，在草稿纸上先用二维思路写递推关系，确认状态转移没有逻辑漏洞后，再压缩成一维写代码。直接上手一维，如果错了很难定位是压缩过程出错还是算法本身出错。二维的代码虽然空间复杂度差一点，但逻辑直观、不容易写出歧义，数据范围小时直接交二维也能过。
如果内存卡得紧，再用一维。转换过程有个检查点：把二维代码中的 dp[i-1] 全部替换成 dp 本身的当前值，然后看循环方向是否需要调整。01背包倒序、完全背包正序，记住这一点，一维压缩基本不会出错。
另外提醒一点：GESP六级环境里的编译器默认是C++14，long long在64位机器上是8字节，足够存一般方案数。但如果题目方案数极大且不要求取模，long long也可能爆掉。遇到这种题，要么用 __int128，要么按题目要求及时取模。以GESP六级的数据范围看，long long 基本都够。
7. 一点实战心得
带过不少学生复习GESP六级，我发现01背包方案数这块的失分，很少是"不会写转移方程"，更多是"条件反射式套模板"带来的低级错误。写模板前，花三十秒问自己三个问题：第一，物品能重复用吗？第二，背包要恰好装满还是不超过容量？第三，题目要不要关心最大价值？三个问题想清楚，代码基本就已经对了一半。
我自己复习动态规划时有个习惯，每学一种模型，就亲手在小黑板上推导一遍二维递推，再压成一维，最后用随机小数据和暴力DFS对拍验证。这个过程看着慢，但能把模型吃透，后期遇到变形题根本不用硬记代码。01背包求方案数、完全背包求方案数、爬楼梯、凑零钱，本质上都共用同一套"加法计数"的思维框架，你把它理解成一棵选择树的节点计数，什么变体都逃不出这个逻辑。
最后分享一个小技巧：考试时如果实在不确定循环方向，就在草稿纸上画一个5列的小表格，手动推两个物品的dp过程，方向对了结果自然对，方向错了5分钟就能发现。别嫌麻烦，这比反复编译提交省时间得多。
