说实话第一次在《信息学奥赛一本通》里看到 1291 题“数字组合”OpenJudge NOI 2.6 2985 是同一道题的时候我是有点懵的。题目说给 N 个正整数每个数最多用一次问有多少种方案能凑成目标值 M。直觉告诉我这应该用 DFS 枚举组合去写结果 N 稍微大一点就超时最后才反应过来这不是组合枚举这是一个“0/1 背包的计数版本”。这篇文章我就把这道题从头到尾拆开讲清楚。从题意里容易踩的坑到为什么 DFS 会挂再到状态转移方程怎么推最后给出可以直接提交的 C 和 Python 代码以及我在 OJ 上真实提交时踩过的几个低级错误。如果你是正在备赛 CSP-J/S、NOIP 的选手或者自学算法时想搞懂“背包计数”这个套路这篇应该能帮你少走不少弯路。1. 先理解题目到底在统计什么数字组合的题意与边界1.1 题目原文只说了一件事题目给了一组正整数比如2 3 5 7目标值是10。你需要从这组数里选若干个每个数只能选一次让它们的和恰好等于10。那么23510是一种方案3710是另一种方案所以答案是2。这就是全部题意没有任何拐弯抹角的地方。它本质上是一个“子集和计数”问题从集合里选一个子集使得子集元素之和等于 M问满足条件的子集有多少个。“每个数最多用一次”这个条件非常关键它直接把问题归类到了 0/1 背包而不是完全背包。很多初学者在状态转移的时候把内层循环写反了结果同一个数被用了无数次答案大得离谱根源就是没有抓住这个“最多一次”的约束。1.2 最容易忽略的两个隐藏约定第一顺序不算新方案。235、325、523在题目里是同一种方案因为选出来的集合是同一个{2,3,5}。如果你用 DFS 按下标顺序递归天然不会重复但如果你用“每次从头枚举下一个数”的写法就很可能把排列数统计进来导致答案偏大。第二数组中重复出现的数字哪怕值相同也算不同个体。比如输入是3 3 7M 是10那么“选第一个 3 7”和“选第二个 3 7”是两种不同的方案。这一点在 DP 里天然成立因为 DP 是按数组下标逐个处理的两个下标不同的 3 会被当成两个独立物品。但如果你用集合去重后再算答案就会不对。还有一个边界问题如果 M 本身就是 0那么“什么也不选”就是唯一方案答案应该是 1。虽然题目一般不会出 M0 的数据但你在推导状态转移方程的时候会发现这个“空集方案数”恰恰是整个 DP 的种子值后面 dp[0]1 就是从这来的。2. 为什么我看到“组合”就想 DFS暴搜失效的根源2.1 2^N 枚举的极限在哪里每个数只有“选”或者“不选”两种状态所以枚举所有子集的复杂度是2^N。当 N20 的时候约 100 万种情况暴力跑一下没问题。当 N30 的时候约 10 亿种情况直接超时。如果出题人把 N 放到 100那2^100这种数字连想都不用想。有人会说我可以排序 剪枝和超过 M 就提前返回。确实能优化不少但最坏情况依然是指数级的。比如所有数字都是 1M 是 50你要从 100 个 1 里选 50 个合法的组合数是 C(100,50)这个数字天文级别DFS 的搜索树会彻底爆炸。那能不能用记忆化搜索可以但你写着写着就会发现记忆化搜索的 memo 表其实就是 DP 的状态表。与其用递归加记忆化不如直接正向推 DP代码更短逻辑也更清晰。2.2 重复子问题才是关键我们来看一个更本质的问题为什么暴力搜索会慢假设数组是1 2 3 4目标 M5。DFS 在递归过程中可能会在“已经处理完前 3 个数、当前和为 3”这个状态停留——路径可以是12也可以是单独一个3。这些路径的前半段不一样但后续的决策完全一样都要看后面的数怎么选。换句话说状态只取决于“处理到第几个数”和“当前已经凑出的和是多少”至于这个和是哪几个数凑出来的根本不重要。这就叫无后效性未来只和当前状态有关和到达这个状态的历史路径无关。一旦发现了无后效性动态规划就是顺理成章的事。我们不需要枚举每一组具体的数只需要记录“凑出某个和 j一共有多少种方式”然后在处理每个新数字时把“选它”和“不选它”两种分支的方案数累加起来。3. 状态定义与转移方程从二维填表到一维压缩3.1 二维 DP 的完整推演定义状态dp[i][j]表示从前 i 个数字中选出若干个数每个最多选一次恰好凑成和为 j 的方案数。这里 i 的范围是 0 到 Nj 的范围是 0 到 M。现在考虑第 i 个数字a[i]它只有两种可能不选那么前 i-1 个数里要凑出 j方案数是dp[i-1][j]选那么前 i-1 个数里要凑出 j-a[i]方案数是dp[i-1][j-a[i]]前提是j a[i]所以转移方程为dp[i][j] dp[i-1][j] dp[i-1][j-a[i]] (j a[i]) dp[i][j] dp[i-1][j] (j a[i])边界条件是dp[0][0] 1表示用 0 个数凑出和 0恰有一种方案什么都不选。dp[0][j] (j0) 0因为没有数字能凑出正数和。我拿一个超级简单的例子手算一遍数组1 2 3M3。i \ j0123010001数111002数211113数31112看最后一行dp[3][3]2两种方案是3和12完全正确。3.2 滚动数组压缩成一维二维数组开dp[N5][M5]在很多题目里没有问题但当你 N 和 M 都到几千的时候空间就不是那么充裕了。观察转移方程可以发现第 i 行只用到了第 i-1 行的数据更早的数据没有任何用处。所以我们完全可以只保留一维数组原地更新。原地更新有一个铁律内层循环必须从大到小遍历。原因很简单如果我们从小到大更新dp[j]那么当算到比较大的 j 时dp[j-a[i]]可能已经被当前这个数字a[i]更新过了。这相当于说“同一个数被用了第二次”违背了每个数最多用一次的约束。所以正确的写法是for i 1 to N: for j M downto a[i]: dp[j] dp[j - a[i]]这样当计算dp[j]时dp[j-a[i]]还是上一轮没考虑当前数字的旧值相当于隐式地完成了“不选当前数”到“选当前数”的加法。4. dp[0]1 到底在算什么以及内层循环为什么必须倒序4.1 dp[0]1 是整个 DP 的“种子”很多初学者看到dp[0]1会疑惑什么都还没选为什么就默认有一种方案因为它是所有单独选择某个数的起点。当你处理数字a[i]时dp[a[i]] dp[0]这里的dp[0]1代表“之前什么都没选现在从空集出发单独选当前这个数”。如果dp[0]0那么整个 DP 就是全 0。为什么因为任何方案都可以追溯到“最开始什么都没选”的状态这个种子一旦丢失所有转移链都会断掉。你可以自己试一下把dp[0]改成 0跑任何样例答案全都是 0。从数学角度说空集的方案数是 1不是 0。这和组合数学里 C(0,0)1 的道理一模一样。4.2 正序更新为什么等于“可以重复选”我再用一个极端简单的例子说明这个坑有多致命。假设数组只有[1]M2。正确答案显然是 0因为只有一个 1凑不出 2。如果内层循环正序写for j 1 to M: dp[j] dp[j-1]初始 dp[0]1。j1 时dp[1] dp[0]得到 dp[1]1j2 时dp[2] dp[1]此时 dp[1] 已经是 1 了所以 dp[2]1最终答案 1这表示“用 1 凑 2”实际是把唯一的一个 1 用了两次。但把循环改成倒序for j M downto 1: dp[j] dp[j-1]j2 时dp[2] dp[1]此时 dp[1] 还是上一轮的 0所以 dp[2]0j1 时dp[1] dp[0]dp[1]1最终答案 0正确。这个例子虽然小但非常说明问题。后者保证每个数字只被使用一次这就是 0/1 背包和完全背包在代码实现上的唯一区别内层循环方向不同。正序对应完全背包同一个数可以重复选倒序对应 0/1 背包每个数最多选一次。5. 可以直接抄的 AC 代码C 和 Python5.1 C 实现题目数据范围一般不会太大方案数可能超过 int所以建议直接用 long long稳一点。#include bits/stdc.h using namespace std; int a[105]; long long dp[10005]; int main() { int n, m; cin n m; for (int i 1; i n; i) { cin a[i]; } dp[0] 1; // 空集算一种方案这是所有转移的起点 for (int i 1; i n; i) { // 内层必须倒序保证每个数只用一次 for (int j m; j a[i]; j--) { dp[j] dp[j - a[i]]; } } cout dp[m] endl; return 0; }这里有个小细节内层循环的起点是j m终点是j a[i]。这样写的效果是自动跳过所有j a[i]的情况既避免了数组越界又减少了几次无意义的迭代。很多新手写成for (int j m; j 0; j--)再在循环体里 if 判断j a[i]语法上没错但循环范围写紧一点性能更好代码也更干净。5.2 Python 实现Python 提交到 OpenJudge 的时候如果用input().split()读数据经常遇到多行输入的格式问题。最稳妥的方式是用sys.stdin.read()一次性把所有整数读进来。import sys def main(): data list(map(int, sys.stdin.read().split())) if not data: return n, m data[0], data[1] a data[2:2 n] dp [0] * (m 1) dp[0] 1 for x in a: for j in range(m, x - 1, -1): dp[j] dp[j - x] print(dp[m]) if __name__ __main__: main()Python 版需要注意range(m, x - 1, -1)的边界。当x大于m时这个循环不会执行也就是那些大于目标值的数字会被自然跳过不会有任何问题。两段代码的核心逻辑完全一样dp[0]1打底外层遍历数字内层倒序更新计数。复杂度是O(N*M)空间是O(M)。6. 我在 OJ 上真实踩过的坑从 TLE、WA 到 AC 的完整排查6.1 看到“组合”就 DFS结果 TLE 到怀疑人生我第一次做这道题时第一反应是写 DFS 枚举下标组合剪枝也加了N20 的小数据跑得飞快结果一提交直接超时。看了题解区才知道这是背包 DP当时心态有点崩。现在回过头看判断是不是背包题其实有个很简单的标准只求方案数不求具体方案且每个元素的使用次数有明确限制就可以往背包上想。数字组合的“每个数最多用一次”就是标准的 0/1 背包约束。6.2 int 放不下答案WA 得莫名奇妙有一版代码逻辑完全正确但用的是int dp[...]结果在大数据点上 WA。后来我写了个对拍脚本用 N20 的小数据和 DFS 暴力程序对比发现答案在部分数据上溢出成了负数才意识到要换long long。方案数的上限有多大最坏情况下如果所有数字之和刚好能凑出大量子集方案数可以达到非常大的级别。比如 N100 的合理数据范围内int 完全可能放不下。所以 C 里直接用long long不要省这个空间。6.3 忘了 dp[0]1整个 DP 全是 0这个错误很低级但很容易犯。当你把 dp 数组整体初始化为 0却忘了单独设置dp[0]1时外层循环里每做一次dp[j] dp[j-a[i]]右边都是 0最后输出永远是 0。我建议在写完 DP 初始化代码后立刻用一组非常小的数据做手算验证比如1 5 3正确答案是 0因为只有一个 3 凑不出 5。再看一组1 3 3正确答案是 1因为直接选 3 本身。如果这时候输出 0那基本就是dp[0]的问题。6.4 对拍验证是救命的调试手段如果你也想验证自己的 DP 是否正确最好的办法是写一个 DFS 暴力程序对拍小数据。这是我在刷题时非常依赖的手段。DFS 暴力版代码如下#include bits/stdc.h using namespace std; int a[25], n, m, ans; void dfs(int idx, int sum) { if (sum m) { ans; return; } if (idx n || sum m) return; dfs(idx 1, sum a[idx]); // 选当前数 dfs(idx 1, sum); // 不选当前数 } int main() { cin n m; for (int i 1; i n; i) cin a[i]; dfs(1, 0); cout ans endl; return 0; }你只需要随机生成 N20 的小数据分别跑 DFS 和 DP对比答案是否一致。只要有一组不一致就说明 DP 写错了而且对拍能帮你快速定位是初始化问题还是循环顺序问题。我自己经常准备这样一组自测数据输入期望输出备注4 10 / 2 3 5 72题目样例1 2 / 10单独一个数不够1 1 / 11单独一个数刚好3 4 / 2 2 11两个 2 凑 42 2 / 1 11两个 1 凑 25 5 / 1 1 1 1 11五个 1 凑 5这几组数据覆盖了“凑不出”“刚好单独成”“重复数字”“全选”等边界情况提交前跑一遍能过滤掉绝大多数低级错误。7. 一题吃透数字组合背后的背包计数家族7.1 变式一数字可以重复选完全背包计数如果把题目改成“每种数字无限供应问凑成 M 有多少种方案”那就是完全背包的计数版本。代码只改一个地方内层循环从倒序变成正序。for (int i 1; i n; i) { for (int j a[i]; j m; j) { // 正序允许重复选 dp[j] dp[j - a[i]]; } }正序更新的含义是当前这个数字可以连续被使用直到超过目标值。这类题的代表是“自然数拆分”把一个正整数拆成若干正整数之和问有多少种拆分方式。这里还需要区分一种更隐蔽的情况如果题目要求“顺序不同算不同方案”比如12和21分别计数那么内外层循环要反过来外层枚举目标值 j内层枚举数字。这个点很多教材都容易讲混我在备赛时专门记过一笔遇到排列计数时再反过来写。7.2 变式二只问能不能凑出可行性背包如果题目只问你“能否凑出 M”不要求方案数那就是可行性背包。状态用 bool 类型转移用或运算。这类题的典型代表是砝码称重给一堆砝码每个只能用一次问能称出多少种不同的重量。你只需要把可行性 DP 跑一遍最后统计 dp[j] 为 true 的 j 有多少个即可。用 C 的 bitset 甚至可以写成一行式优化bitset10005 bs; bs[0] 1; for (int i 1; i n; i) { bs | bs a[i]; }左移操作的含义就是“每个已有重量加上当前砝码后能到达的新重量”。这个技巧在竞赛里经常用来压时间但初学者还是先把普通 DP 弄明白再说。7.3 变式三输出具体方案回溯如果题目不仅要方案数还要求输出所有方案那 DP 的计数值就不够用了需要在 DP 跑完后回溯。回溯的思路是从dp[i][j]往回推如果dp[i-1][j]也为 1说明有一种方案没选第 i 个数如果dp[i-1][j-a[i]]也为 1说明有一种方案选了第 i 个数。沿着这些分支递归下去就能还原出所有具体组合。注意回溯版必须保留二维 DP 表不能压缩成一维因为你需要知道每一步的决策来源。输出方案数的题目通常 N 很小二维数组的空间可以接受。我自己在带集训队的时候经常用这道题给刚学背包的选手做“跳板”。能把数字组合完全吃透后面遇到二维费用背包、分组背包、依赖背包至少不会对状态设计发怵。毕竟它们的内核都是同一套“选或不选”的决策逻辑只是约束条件在叠加而已。这道题本身不难但它站在 0/1 背包和计数 DP 的交界点上。你把它彻底弄明白再回头去看那些“换皮题”就会发现很多题目改来改去最终都是让你维护一张 dp 表填表顺序对了答案自然就出来了。