信息学奥赛一本通 1291 与 OpenJudge NOI 2.6 2985这两套题号指向的是同一道题目数字组合。它是很多 OIer 学过 0-1 背包之后的“计数版”练习也是不少人在动态规划入门时第一次发现“原来方案数也能用 DP 算”的题。今天我不打算简单贴一份代码而是把这道题的推导过程、实现细节和容易出错的地方全部拆开讲一遍。无论你是刚刷完一本通的初二学生还是带队的竞赛教练这篇应该都能给你一点参考。1. 题目回顾数字组合到底问的是什么1.1 题面信息与样例演示数字组合这题的题面很简短给出一组正整数问从中选出若干个数使它们的和恰好等于 M一共有多少种选法。输出只需要一个整数也就是方案数。第一行输入两个整数 N 和 M代表数字个数和目标总和第二行输入 N 个整数即待选的数字。来看一个最常用的样例4 4 1 1 2 2输出3为什么答案是 3把 4 个数字按输入顺序记为第 1 个 1、第 2 个 1、第 1 个 2、第 2 个 2能达到和 4 的选法有第 1 个 1 第 2 个 1 第 1 个 2第 1 个 1 第 2 个 1 第 2 个 2第 1 个 2 第 2 个 2正好 3 种。要注意这里虽然两个数字的值相同但它们位于输入的不同位置因此在计数时会被当作不同选择。我第一次学的时候就在这个细节上栽过跟头总以为两个 1 可以合并结果怎么对都对不上样例。1.2 为什么暴力枚举不是正确答案很多人拿到题的第一反应是 DFS用一个递归函数依次决定每个数字选或不选同时维护当前和等于 M 就计数。这个思路没有错也很好写但代价是指数级的。N 个数字每个数字选或不选枚举所有子集需要 2^N 种情况。当 N20 时一百万次运算勉强能在某些平台上跑完N30 就到了十亿级别基本超时如果 N 继续增大到 100 甚至更大指数级枚举完全没有活路。而题目给的数据范围恰恰就是冲着“不能用指数级枚举”来的。所以需要一种能利用“前面算过的结果”的算法把复杂度降下来。DP 就是干这个的通过把大问题拆成一层层小状态每个状态只算一次避免重复递归展开。2. 动态规划推导方案数是怎么递推出来的2.1 定义状态 dp[i][j]前 i 个数凑出 j 的方案数设 dp[i][j] 表示只考虑前 i 个数字从中选出若干个使它们的和恰好等于 j 的方案数。两个维度各有各的含义。i 用来限制“当前可用的数字范围”从 0 到 Nj 用来记录“当前拼出的总和”从 0 到 M。最后要的答案就是 dp[N][M]也就是所有 N 个数字都能用的时候恰好凑出 M 的方案总数。这个定义也是背包类 DP 的通用模板二维状态中一维是“前几个物品”或者说“处理到哪个物品”另一维是“容量/总和/代价”。一旦状态定义清楚后面的转移就顺理成章。2.2 状态转移方程不选第 i 个数还是选第 i 个数处理第 i 个数字 a[i] 时它只有两种归属不参与组合或者参与组合。不选 a[i]那么前 i-1 个数必须已经凑出了 j方案数是 dp[i-1][j]。选 a[i]那么前 i-1 个数必须凑出 j-a[i]方案数是 dp[i-1][j-a[i]]前提是 j 不小于 a[i]。这两种情况互斥且覆盖所有可能所以直接把方案数加起来dp[i][j] dp[i-1][j] j a[i] 时 dp[i][j] dp[i-1][j] dp[i-1][j-a[i]] j a[i] 时以样例为例四个数字依次为 1、1、2、2M4完整的 dp 表如下i\j012340空100001选 1110002再选 1121003再选 2122214再选 212343看表格最后一列dp[4][4]3正好对应样例输出。每一行从左到右看也能感受到状态如何一层层叠加当引入第 4 个数字 2 之后dp[4][2] 从上一行的 2 增加到 3多出来的一种就来自“选第 4 个 2同时前 3 个数凑 0”。2.3 初始化要点dp[0][0]1 是源头初始化是整个 DP 里最容易被忽视、却最致命的一步。dp[0][0] 必须等于 1表示前 0 个数凑出总和 0只有“什么都不选”这一种方式。而 dp[0][j]j0必须等于 0因为没有任何数字可选时不可能凑出正数。很多人会把整个 dp 数组初始化成 0然后就忘了设置 dp[0][0]1结果整个表格全是 0答案永远输出 0。也有一些人把 dp[i][0] 全填成 1这同样不对虽然每行确实会通过转移天然更新出 dp[i][0]1但提前手动填满会干扰转移语义在部分题目的变形中会造成计数偏差。正确的做法是只初始化 dp[0][0]1其余全为 0让转移去自己生成后面的状态。3. 代码实现从二维到一维再到 Python3.1 C 二维数组版思路最直白的写法先上最符合推导过程的二维写法#include iostream #include vector using namespace std; int main() { int n, m; cin n m; vectorint a(n 1); for (int i 1; i n; i) { cin a[i]; } vectorvectorlong long dp(n 1, vectorlong long(m 1, 0)); dp[0][0] 1; for (int i 1; i n; i) { for (int j 0; j m; j) { dp[i][j] dp[i - 1][j]; if (j a[i]) { dp[i][j] dp[i - 1][j - a[i]]; } } } cout dp[n][m] endl; return 0; }这里用 long long 而不是 int原因后面会专门讲。二维数组版本最容易和推导过程对照适合在初学阶段用来理解状态转移也方便日后改造成“输出路径”的版本因为每一层的数据都被完整保存了下来。3.2 一维滚动数组版空间复杂度从 O(N*M) 降到 O(M)观察转移方程会发现dp[i] 这一行只依赖 dp[i-1] 这一行再往前的数据没有用处。既然每个 i 只是按顺序把上一行“覆盖”成新行就可以只用一维数组滚动更新。真正需要注意的是内层循环的方向。如果 j 从 0 向 M 从小到大枚举那么 dp[j-a[i]] 可能已经被当前这轮也就是当前这个 i更新过了等于说 a[i] 被重复使用了多次。为了让每个数字只能选一次必须让 j 从 M 往 a[i] 的方向倒着枚举#include iostream #include vector using namespace std; int main() { int n, m; cin n m; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } vectorlong long dp(m 1, 0); dp[0] 1; for (int i 0; i n; i) { for (int j m; j a[i]; j--) { dp[j] dp[j - a[i]]; } } cout dp[m] endl; return 0; }画一张图就很好理解一维数组里倒序循环时 dp[j-a[i]] 一定还是上一轮前 i-1 个数字算出来的结果等更新完 dp[j]后面更大的 j 引用的也不是会被破坏的最新值。逆序是 0-1 背包计数和完全背包计数的分水岭这句结论值得记下来。3.3 Python 版本与语言实现细节Python 写这道题同样简洁n, m map(int, input().split()) a list(map(int, input().split())) 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])读入时注意第二行可能有多余空格用 split 会自动处理。Python 的整数不会溢出所以不需要担心 long long但如果你在 C 里用 int当方案数超过约 21 亿时就会变成负数这是竞赛里非常常见的翻车现场。竞赛环境下计数类 DP 我通常直接定义 long long省得最后去猜哪里爆了。4. 常见错误与现场调试这些问题我全都见过4.1 内层循环方向写反0-1 背包变成完全背包这是出现频率第一名。一维写法里如果把内层循环写成for (int j a[i]; j m; j) { dp[j] dp[j - a[i]]; }每个数字就会被当成“可以无限使用”来处理。用最极端的一组数据来验证只有一个数字 1目标是 2。逆序循环的结果是 dp[2]0因为一个 1 不可能凑出 2正确。顺序循环的结果是 dp[2]1因为它先更新了 dp[1]1再用 dp[1] 更新 dp[2]等于同一个 1 被用了两次。看到 dp 值异常偏大或者感觉“多算了好几种”第一反应就是查内层循环方向。这个错误我在学生作业里改过不下十遍自查的时候建议专门准备一个“只有一个数字等于 1M 等于 3”的样例正确输出应该永远是 0。4.2 dp[0] 初始化和空集合语义的坑如果把 dp[0] 初始化为 0最终结果永远是 0。如果整个数组初始化成 1又会让每一种组合都被额外多算一遍。只有 dp[0]1 才符合语义空集合是一种合法的选择它贡献了所有组合的“起点”。另外当输入的数字里有 0 时情况会变得微妙。数字 0 可以选也可以不选而且不影响总和会在计数里造成翻倍效果。大部分原题数据会保证所有数为正整数所以这个场景不常见如果遇到允许 0 的变体需要单独讨论。在标准解法里不需要专门处理 0 的情况。4.3 数据范围和结果类型用 int 输出负数数字组合的答案不是取模问题而是实实在在的大整数统计。只要数字数量稍微大一点方案数就可能膨胀得非常快。比如 N40、M20、所有数字都是 1答案就是 C(40, 20)约 1378 亿int 早就装不下了。因此 C 里请无脑使用 long long。判题平台如果严格要求不取模用 long long 基本能覆盖常见范围如果题目说明要取模那就每一步更新时都对模数取余。交题之前还可以利用“所有数字都大于 M”“只有一个数字等于 M”这两组极限数据做自测前者答案应该是 0后者答案应该是 1。这两组数据能帮你排除掉八成的基础错误。5. 从数字组合到一类 DP 题引申与练习建议5.1 允许重复选择的变体换一个遍历方向即可如果把题目改成“每个数字可以重复使用问凑出 M 有多少种方案”那就是完全背包计数。实现上只改一个地方内层循环从 a[i] 到 M 正着跑。for x in a: for j in range(x, m 1): dp[j] dp[j - x]正序的原因正好和前面相反我们希望 dp[j-x] 已经被本轮更新过这样同一个 x 才能被再次使用。这种变体在找零钱、换硬币问题里很常见把数字组合吃透后再学完全背包只需要理解这一步差异。5.2 需要输出具体组合方案时用带路径回溯的 DP如果题目要求不是输出方案数而是把每种组合列出来DP 就只完成了第一半。可以先开二维数组保存完整 dp 表然后从 dp[N][M] 往回走如果 dp[i-1][j] 不为 0说明存在不选第 i 个数字的方案向 (i-1, j) 转移。如果 j a[i] 且 dp[i-1][j-a[i]] 不为 0说明存在选第 i 个数字的方案记录 i 后向 (i-1, j-a[i]) 转移。因为方案数可能很多输出路径时要注意去重如果两种路径到达同一个 (i, j)实际输出的是同一组数字可以在回溯时只选择一条分支或者用集合去重。这一部分一般不会出现在“只求方案数”的原题里但却是 DP 技术应用中很实用的一项能力。5.3 识别“方案数 DP”的小套路数字组合背后是一类很典型的题目结构给一堆元素问选若干元素形成某种条件一共有多少种选法。一旦看到这种结构按下面三步走基本不会错第一步确认每个元素是否只能用一次。能用一次是 0-1 背包计数能用无限次是完全背包计数。第二步把“目标和 M”设计成 DP 的容量维度把“前 i 个元素”设计成物品维度。第三步初始化 dp[0] 1或 dp[0][0] 1按逆序或正序更新容量循环最终答案查 dp[M]。这个方法不仅能解数字组合还能迁移到很多题目上。比如“选若干物品填满容量 M”“从字符串中选字符拼成目标串”这类计数问题骨架都是同一套。练完数字组合后可以再找一两道完全背包计数和标准 0-1 背包题做对比自己写一遍三种循环方向感受会比只看题解深很多。最后分享一个交题前的习惯我会先用“一个数字 1目标 3”验证是否误用正序再用“一个数字 3目标 3”验证初始化是否正确最后用“所有数字都远大于 M”验证输出是不是 0。这三组小数据加起来不到 5 分钟却能拦住绝大多数低级失误。动态规划的上手阶段比写对公式更重要的其实就是这些不起眼的边界检查。