1291数字组合详解：0/1背包求方案数的动态规划思路-北京尧图网络

很多刚开始刷信息学奥赛一本通的同学做到动态规划这一章时第一道真正让人卡住的题往往不是最难的“背包九讲”反而是这道看似人畜无害的“1291数字组合”OpenJudge 上的编号是 2985。题目描述很短给定N个正整数从中选出若干个数使它们的和等于M求有多少种不同的选择方案。我第一次见到这题时第一反应是搜索DFS枚举每个数选或不选N最大到20还能应付可题目范围是N≤100M≤10000搜索瞬间爆炸。后来才知道这题的隐藏身份其实是“0/1背包求方案数”而且是背包问题里最基础的一种变体。今天就把这道题从原理到代码彻底拆开讲清楚包括状态定义怎么来的、为什么初始化是dp[0]1、二维转一维时为什么内层要倒序以及测试中常见的几个坑。无论是准备NOIP、CSP-J/S还是单纯想理解动态规划的同学这篇都能让你少吃点苦头。1. 题目本质从“选数凑和”到背包模型的转换1.1 先看懂题目在说什么题目给了一组数字比如样例中的 5 个数1, 2, 3, 4, 5目标总和 M5。合法的选择方案有很多直接选 5选 1 和 4选 2 和 3选 1 和 2 和 3 1236不对应该是 1 和 2 和 3 中的某两个仔细列一下应该是 1236不等于5所以不合法。选 1 和 2 和 ? 不行选 1 和 3 和 ? 134加26加48加59。实际上列举{5}、{1,4}、{2,3}。所以答案是 3。每个数只能选一次这天然符合0/1背包的特征背包容量是M每个数字是物品物品体积等于它的值物品价值不存在或者说价值就是方案数要求恰好装满背包的方案总数。1.2 为什么用动态规划而不是搜索很多初学者会问N100直接搜索不行吗可以算一下每个数有选和不选两种状态理论上组合数是2^N也就是2的100次方这个数量级远远超出CPU能在有限时间内处理的范围。即使用剪枝优化最坏情况还是会卡死。动态规划的思路本质是“用空间换时间”。它记录下“在已经处理了一部分数字后凑出某个和有多少种方案”。这样同一子问题只会计算一次时间复杂度只有O(N×M)也就是100×10000100万次运算在竞赛环境里连0.01秒都用不到。1.3 动态规划方程是怎么推出来的核心状态定义dp[j] 表示在当前已经考虑过的数字中选出若干个数使其和恰好为 j 的方案数。假设现在遍历到第 i 个数字 num[i]对于每个目标和 j分两种情况不选第 i 个数那么凑成 j 的方案数不变还是 dp_old[j]。选第 i 个数那么需要先凑成 j - num[i]再加上第 i 个数方案数为 dp_old[j - num[i]]。因为“不选”和“选”是两种不同的方案所以它们相加dp_new[j] dp_old[j] dp_old[j - num[i]]这就是状态转移方程。边界条件是 dp[0]1因为凑出和为0只有一种方案什么都不选。其他 dp[j] 初始为0。如果不使用滚动数组而是开二维数组 dp[i][j] 表示前 i 个数中选取若干和为 j 的方案数那么转移方程也很直观dp[i][j] dp[i-1][j] (j num[i] ? dp[i-1][j-num[i]] : 0)二维的写法更符合逻辑推导过程适合初学者理解。一维滚动数组是在其基础上进行空间优化。2. 核心细节解析从二维到一维从初始化到循环顺序2.1 二维DP的完整推导与实现用二维数组是为了把“前i个数”这一维度显式保存下来。先看核心代码#include iostream using namespace std; int dp[105][10005]; int a[105]; int main() { int n, m; cin n m; for (int i 1; i n; i) cin a[i]; dp[0][0] 1; // 前0个数凑出和为0方案数为1 for (int i 1; i n; i) { for (int j 0; j m; j) { dp[i][j] dp[i-1][j]; // 不选第i个数 if (j a[i]) { dp[i][j] dp[i-1][j - a[i]]; // 选第i个数 } } } cout dp[n][m] endl; return 0; }这里内层循环 j 从 0 遍历到 m。当 j a[i] 时无法选第 i 个数所以方案数就是上一层直接复制下来。当 j a[i] 时要把“选”和“不选”两种情况的方案数加起来。二维 DP 的空间是 (n1)×(m1)当 N100、M10000 时大概是 101×10001 个 int也就是约400KB完全可以接受。但如果 M 大到10^7级别就必须用一维数组优化。2.2 一维滚动数组为什么内层循环必须倒序一维优化的核心是用同一个数组反复更新每次迭代 i 相当于把 dp 数组覆盖成最新状态。代码长这样#include iostream using namespace std; int dp[10005]; int a[105]; 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 递减到 a[i]而不是从 a[i] 递增到 m这里藏着一个经典的“01背包”陷阱。如果正序循环for (int j a[i]; j m; j) { dp[j] dp[j - a[i]]; }假设 a[i]2dp[2] 更新后变成 dp[0] dp[2]原来dp[2]。等到 j4 时dp[4] 会使用 dp[2]但此时的 dp[2] 可能已经被本轮更新过了也就是说它已经包含了“选用当前第 i 个数”的方案。于是 dp[4] 就可能出现“用了两次第 i 个数”的情况导致算法从 0/1 背包退化成完全背包方案数被放大。倒序循环时j 从大到小dp[j-a[i]] 一定比 dp[j] 后更新因为 j-a[i] j且在递减的循环中j-a[i]还没轮到更新所以使用的仍是上一轮 i-1 的状态这样就保证了每个数字最多被选一次。我给学生的口诀是“01背包倒序完全背包正序空间压缩要小心正序就会把物品用无限次。” 配合这个直观的错误样例一般都能理解。2.3 初始化为什么要 dp[0] 1 而不是 0这是初学者最常问的问题“dp[0] 不是什么都不选吗那应该算一种方案吗” 答案是必须算一种。因为递推关系需要这个“基底”。想象一下当你遇到一个数字 num它恰好等于目标 j那么选它本身就是一种合法方案这种方案应该从 dp[j - num] 推导出来也就是从 dp[0] 推出来。如果 dp[0]0那所有“单个数恰好等于这个和”的方案都会消失整道题直接废掉。从组合数学的角度看空子集的元素和为0这是一个合法的子集。而当我们只关心“非空选择”时最终答案里 dp[0] 本身并不会被计入因为目标和 M 一般大于0所以保留它是准确且安全的。另一个容易混淆的点是如果题目有特殊要求“至少选一个数”那答案应该输出 dp[m] - dp[0]但本题不需要因为目标和 M 必然大于0空集不可能凑出正数。3. 实操过程与核心环节实现从输入到输出的完整落地3.1 题目输入输出的坑多组数据问题OpenJudge 的 2985 原题和一本通 1291 中数字组合这题的输入格式是第一行N M 第二行N 个正整数但实际评测时我遇到过几种变体比如有些题目没有明确说明是否多组测试数据或者行尾有空格这些都不算问题。真正要小心的是使用 scanf 或 cin 时有没有正确处理空格和换行。比如scanf(%d %d, n, m); for (int i 1; i n; i) scanf(%d, a[i]);这里注意 a 数组的下标从1开始便于逻辑对齐。如果你习惯从0开始也可以但循环内对应关系要调整清楚。输出就是一个整数代表方案总数。注意方案总数可能很大超过 int 范围吗题目描述中通常 N 的范围不超过100M不超过10000数字本身也不超过10000理论上最多方案数能到 2^100显然大得离谱。不过本题的 M 限制让可行方案数不会无限膨胀但用 int 保存依然可能溢出。稳妥的做法是用 long long 甚至更高精度吗实际上一本通和 OpenJudge 官方数据下 int 能过那是因为给定的数据范围并不苛刻但为了安全我建议开 long long反正内存够用。下面给出一个标准、完整的 long long 版本方便直接提交#include bits/stdc.h using namespace std; long long dp[10005]; int a[105]; int main() { int n, m; scanf(%d %d, n, m); for (int i 1; i n; i) scanf(%d, 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]]; } } printf(%lld\n, dp[m]); return 0; }如果编译器支持也可以用long long dp[10005];。注意输出格式要和类型匹配%lld对应 long long。3.2 手推一遍样例理解状态的演化过程只看代码很难体会到 DP 表是怎么填的。我们把样例跑一遍。初始dp [1, 0, 0, 0, 0, 0] // 下标0~5第1个数 a[1]1从 j5 倒序到1j5: dp[5] dp[4] 0j4: dp[4] dp[3] 0j3: dp[3] dp[2] 0j2: dp[2] dp[1] 0j1: dp[1] dp[0] 1更新后dp [1, 1, 0, 0, 0, 0]。含义用数字1可以凑出0和1各1种方案。第2个数 a[2]2倒序遍历j5: dp[5] dp[3] 0j4: dp[4] dp[2] 0j3: dp[3] dp[1] 011j2: dp[2] dp[0] 011更新后dp [1, 1, 1, 1, 0, 0]。含义用数字1和2可以凑出0、1、2、3各1种。第3个数 a[3]3j5: dp[5] dp[2] 011即235j4: dp[4] dp[1] 011即134j3: dp[3] dp[0] 112一种是直接选3一种是12更新后dp [1, 1, 1, 2, 1, 1]。第4个数 a[4]4j5: dp[5] dp[1] 112即145j4: dp[4] dp[0] 112一种直接选4一种134更新后dp [1, 1, 1, 2, 2, 2]。第5个数 a[5]5j5: dp[5] dp[0] 213新增直接选5最终 dp[5]3答案正确。这个手推过程建议大家自己动笔写一遍。只有亲手填过 DP 表以后遇到类似“子集求和”的变形题才能一眼看穿状态设计。3.3 另一种常见变形输出具体方案怎么办有些同学会问如果题目不是求方案数而是要求输出所有满足条件的组合类似 LeetCode 的 Combination Sum那该怎么办那就不能只用 DP 了因为 DP 的状态压缩掉了“具体是哪些数”的信息只能知道数量不能回溯组合。此时可以用记忆化搜索或者回溯法void dfs(int idx, int sum, vectorint path) { if (sum m) return; if (sum m) { ans.push_back(path); return; } if (idx n) return; // 不选当前数 dfs(idx 1, sum, path); // 选当前数 path.push_back(a[idx]); dfs(idx 1, sum a[idx], path); path.pop_back(); }不过竞赛题目一般只要求方案数所以 DP 才是标准解法。知道这个区别对理解 DP 的适用边界很有帮助。3.4 与“数字组合”相关的经典扩展题这类“给定数组求凑出目标和的方案数”的问题在竞赛里有一整族。理解这一道等于打开了背包方案数的大门。完全背包求方案数如果每个数字可以无限次使用这就是完全背包问题。内层循环改成正序即可。典型题目如 OpenJudge 的“货币系统”或者 LeetCode 的 518. 零钱兑换 II。二维费用背包求方案数如果每个物品有两个维度比如重量和体积状态就要开两维转移时多套一层循环。排列数 vs 组合数数字组合题中顺序不同的选择视为同一种因为选择的是“子集”。但如果是“排列数”比如从数字中选若干个数排成一个序列使和为M那就要注意内外层循环的顺序具体不展开先记得这个区分。4. 常见问题与排查技巧实录4.1 样例过了提交却全WA先检查初始化经常有学生写完代码自测样例输出3感觉很完美一提交 OpenJudge 就全错。我让他们先把dp[0]改成0试试结果答案全变0证明初始化影响巨大。但是样例过了全WA还有一种常见原因数组开小了。我看到过一个离谱的错误dp[100]但 M 最大是10000一访问就越界本地运行可能不报错但评测机上直接 RE 或莫名 WA。竞赛里数组越界是玄学问题建议一律开成dp[10005]甚至更大千万不要卡着上限开。如果确认不是这两个问题那八成是循环边界写错了。比如写成了for (int j m; j a[i]; j--)丢掉了 ja[i] 这个关键情况导致所有单个数恰好等于目标的方案全部丢失。正确写法是j a[i]。4.2 不知道用 int 还是 long long 的纠结题目没有明说答案范围很多同学就按 int 交了。事实上在一些数据较弱的OJ上 int 能过但在某些强化数据下会 WA。根据经验方案数的增长速度远超直觉即使是 N100、M10000、数字范围1~10000最坏情况下合法方案数也可能是天文数字。虽然官方测试点大多有意避开爆 int 的数据但用 long long 是零成本的还能避免用%d输出 long long 的坑不过 printf 里写%lld就行。如果是更极端的范围比如 N1000、M100000long long 也可能溢出但那是题目设计的问题超出竞赛常规范围了。4.3 内层循环正序的经典错误我在上课时专门设计过一个对比实验把一道题用错误的“正序”写法和正确的“倒序”写法分别提交让同学们看输出差异。有个非常典型的例子数字序列2, 3, 5目标 M6。正确答案是 2 种222不行同一个2最多用一次。2? 不对33但3也只有一个。6没有6。所以正确答案应该是0种。倒序 DP 得到 0。而如果内层正序循环dp[6] 会通过 dp[4] 和 dp[3] 层层叠加算出多个重复使用数字的方案最后得到错误的大于0的答案。这个实验说明正序循环会“复活”已经用过的数字把01背包变成完全背包。如果你发现答案偏大优先检查这里。4.4 调试技巧打印 DP 表遇到复杂一点的 DP最好的调试办法不是对着屏幕冥想而是把 DP 表打印出来逐行核对。以 N3, M5数字为 1 2 2 为例打印每次外层循环后的 dp 数组就能看到状态如何一步步收敛。这种方法比单纯用 gdb 打断点更直观。建议在本地调试时写一个小函数void print_dp() { for (int j 0; j m; j) cout dp[j] ; cout endl; }每处理完一个数调用一次观察数组变化是否符合预期。4.5 多组输入的处理OpenJudge 有些题不会一次性给完数据题目会写“依次处理到文件结束”。不过本题通常只含一组数据但以防万一可以这样读while (scanf(%d %d, n, m) ! EOF) { memset(dp, 0, sizeof(dp)); dp[0] 1; for (int i 1; i n; i) scanf(%d, a[i]); ... printf(%lld\n, dp[m]); }注意每次循环前要memset清空 dp 数组否则上一次的结果会残留造成数据污染。5. 实战演练从暴力搜索到动态规划的思维进化5.1 先用DFS跑通小数据找感觉如果你第一次接触这道题不要急着背模板。我建议先用 DFS 写一版暴力哪怕只为了验证答案。int ans 0; void dfs(int idx, int sum) { if (sum m) { ans; return; } if (sum m || idx n) return; dfs(idx 1, sum); // 不选 dfs(idx 1, sum a[idx]); // 选 }这个版本在 N≤20 时可以运行N30 就开始吃力。但它能帮你建立“选/不选”的直觉和 DP 的状态转移一一对应。很多同学看不懂dp[j] dp[j-a[i]]到底在干嘛其实它就是把 DFS 里左右两个分支合并成了查表。从 DFS 到 DP 的转化我习惯用“记忆化搜索”作为中间桥梁。定义一个函数f(i, j)表示前 i 个数凑出 j 的方案数直接递归int f(int i, int j) { if (i 0) return j 0 ? 1 : 0; if (dp[i][j] ! -1) return dp[i][j]; int res f(i-1, j); if (j a[i]) res f(i-1, j - a[i]); return dp[i][j] res; }注意到这个递归函数和二维 DP 的转移方程长得一模一样。一旦理解了记忆化搜索再看二维 DP 就是顺理成章了。这个方法也适合那些始终觉得“递推式来得太突然”的同学。5.2 时间复杂度的关键判断为什么 O(N×M) 可行一道 DP 题能不能用核心在于状态数和转移代价。本体的状态数是 (N1) × (M1) ≈ 101×10001 ≈ 101万每个状态转移 O(1)总操作 101万次。CPU 每秒轻松处理亿级运算所以完全没问题。有人可能会想M 最大10000那数组大小是 10000没问题。但如果遇到 M 为1e9 的大容量就必须换思路比如用折半搜索Meet in the middle不过那是另一个话题了。竞赛中很多题目会在数据范围上设计陷阱看到 N 和 M 的取值第一反应应该是判断算法量级是否匹配。5.3 对比其他思路为什么不用深搜剪枝也许你会想N100但数字如果都很大剪枝会不会很快事实上最坏情况可以构造很多小数字比如全是1此时和为 M 的方案数量很大剪枝也救不了。而且 DFS 即使找到了所有方案还要花时间枚举输出而 DP 只计数运算量小得多。还有一种思路是位运算组合枚举只能应付 N 很小的情况比如 N≤25 可以折半搜索但 N100 时完全不可行。所以在竞赛考察范围内0/1背包 DP 是唯一高效且标准的解法。6. 个人经验与高频误区总结这道数字组合题说难不难但每年都有不少学生在它上面栽跟头。我印象最深的三个误区这里统一讲透。第一个误区和dp[0]有关。有学生认为“什么都不选不算一种方案”强行把 dp[0] 设为0结果样例能过因为样例答案3恰好不包含0换一组数据就错。其实dp[0]1的意义在数学上是“空集是任何集合的子集”在程序上则承担着递推起点的作用。强调再多都不为过遇到背包求方案数初始化永远先写dp[0]1。第二个误区是循环边界写错。和只差一个等于号却能决定你是否漏掉“单个数正好构成目标”的所有方案。这种隐蔽 bug 在样例数据小的时候不一定能暴露因为样例里可能没有“目标恰好等于某个数字”的情况。我的建议是专门构造n1, a[0]M的测试点如果输出0那一定是边界问题。第三个误区是企图用搜索“优化优化就能过”。我见过很多学生在 Time Limit Exceeded 之后不断加剪枝、加记忆化、改迭代函数最后发现其实和 DP 已经差不多了却绕了一大圈。不如直接理解状态设计一次写对。如果你已经掌握了这道题强烈建议你立刻去刷两道同型题来巩固一本通里同章节的“完全背包问题”和“潜水员”都是背包求最值的变体而“货币系统”和“数的划分”则和方案数有关。把这一类题放在一起做对比总结你会突然发现原来“选或不选”这四个字能衍生出这么多变化。最后再分享一个实用技巧比赛时如果担心 DP 数组越界或结果溢出可以在数组外面加一圈哨兵比如dp[10005]开成dp[10010]把循环边界写成j a[i]这样就算某个数等于10000也能安全访问 dp[0]。这种事看似不起眼但在考场争分夺秒时能帮你少一次 RE 的惨痛教训。数字组合这道题吃透了它你就摸到了背包问题的门槛。

1291数字组合详解：0/1背包求方案数的动态规划思路

相关推荐

Status Deck：基于ESP32的开发者状态感知系统设计与实现

电子信息专业四年规划：嵌入式与芯片方向学习路径

NIST SP 800-22随机数测试工具完整指南：下载、编译、运行与结果解读

更多资讯

如何用 Win11Debloat 移除 Windows 11 预装应用和关闭遥测（附完整回滚步骤）

抖音批量下载工具指南：douyin-downloader 从单条视频到主页合集上手

Lovefield 外键约束与引用完整性详解：RESTRICT/CASCADE 动作模式与约束时序

ktlint 制品签名实战：基于 SIGNING.md 在本机构建并验证 GPG 签名产物

Channels 2.3.0 请求体处理重构：AsgiHandler 基于 SpooledTemporaryFile 的内存优化与兼容性迁移指南

react-day-picker 的 Hijri 阿拉伯语区域设置：arSA 本地化变量源码解析与实战

今日更新

基于sEMG与IMU的手语手势识别：从数据采集到实时部署避坑指南

装配车间MES落地指南：SimpleMES工单流转、BOM与齐套检查实战

AI获客怎样减少重复线索？意客AI的原文复用与版本筛选

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？