在洛谷练动态规划题单的人十有八九会撞上 P2840 纸币问题 2。这道题看上去平平无奇给你几种面额的纸币每种无限张问凑出某个金额有多少种方案。可就是这么一道基础题每次提交总能看到一群人卡在“组合数算重复”上反复 WA 之后才恍然大悟。这篇文章就围绕这道题展开把从读题到 AC 的全过程、背后的状态设计逻辑、循环顺序的坑都捋一遍适合刚入坑 DP、准备系统刷题单的新手也适合想一口气理清“完全背包求方案数”这个知识点的朋友。1. 题目本质这不是“数钱”是“数方案”1.1 先把原题转换成一句话P2840 的题面很简洁有 n 种纸币第 i 种面额为 a[i]每种纸币都有无数张问组成 M 元一共有多少种不同的方案。最终答案需要对某个模数取模通常是 1e97。我先提醒一个容易搞混的点题目说的是“纸币问题 2”那“纸币问题 1”是什么常见题库里的编号顺序是——纸币问题 1 往往只问“能否凑出 M”或者问最少需要多少张而纸币问题 2 专门问“方案总数”纸币问题 3 则可能是限定张数上限的背包变体。所以这道题的核心诉求非常明确给的是“方案数”不是“最优张数”也不是“存在性判断”。1.2 方案数的语义组合还是排列这是整个题目最大的隐含判断。假设你有两种纸币1 元和 2 元需要凑 3 元。用“1 张 1 元 1 张 2 元”和“1 张 2 元 1 张 1 元”在现实世界里是同一种换钱方式。衣服包装、取钱顺序没有任何意义所以题目默认“不考虑选取顺序”即统计的组合方案数而不是排列方案数。这也是“纸币问题 2 ”和“爬楼梯”类题目的根本区别。爬楼梯每次走 1 步或 2 步问走到第 3 级有多少种方法那“12”和“21”算两种因为动作顺序不同。纸币问题是按“面额种类”分组只要每种面额取的数量一样不管先取哪种都只能算一种。如果你拿爬楼梯的思路直接套样例可能都过不了——准确说过得了小样例但一旦面额种类多、金额大就会多算一大片。1.3 数据范围决定了算法方向注意观察题目的限制n 通常在几十到几百之间M 通常在几千到几万之间。这个范围直接排除 DFS 暴搜因为组合数的爆炸速度根本不是人能枚举的。即便是用递归 记忆化也需要先想清楚状态维度最自然的还是动态规划复杂度 O(n * M)百万级别完全在可接受范围内。所以这道题本质上就是“完全背包求方案数”的模板题。背过完全背包求最大价值的同学只需要把“取最大值”改成“累加方案数”再小心处理循环方向就能 AC。2. 动态规划的设计状态、转移和初始化2.1 状态定义dp[j] 表示什么定义一维数组dp[j] 凑成金额 j 的方案总数有人会问为什么不需要二维 dp[i][j] 表示“前 i 种纸币凑 j”的方案数因为这里每种纸币无限张没有张数限制使用滚动数组完全可以压缩掉“纸币种类”那一维。但压缩之前必须先理解二维状态下的转移逻辑否则后面容易糊涂。在二维版本中设 dp[i][j] 表示使用前 i 种纸币第 1 到第 i 种凑出金额 j 的方案数。转移时考虑第 i 种纸币取 k 张k 的范围是 0 到 floor(j / a[i])dp[i][j] sum( dp[i-1][j - k * a[i]] ) 对所有合法 k这个式子才是原始的“完全背包方案数”公式。一维版本是它的空间优化结果但转移语义上必须保证每个 dp[j] 只能在处理完一种面额后再更新否则就会把不同排列顺序误认为不同方案。2.2 转移方程一维完全背包写法按“外层循环面额内层循环金额”的顺序更新for i 1 to n: for j a[i] to M: dp[j] (dp[j] dp[j - a[i]]) % MOD初始化时dp[0] 1理由是凑 0 元只有一种方案就是哪张纸币都不拿。这个初始化是所有背包计数问题的起点也是很多人忽略、导致最后答案全 0 的元凶。2.3 为什么要先枚举面额再枚举金额这可能是整道题最“要命”的细节。如果先枚举金额再枚举面额写成for j 1 to M: for i 1 to n: if j a[i]: dp[j] dp[j - a[i]]你算出来的就是排列数。举个例子面额 1 和 2凑 3先金额后种类的方式会得到dp[3] dp[2] dp[1]从面额1转移 ... 其中 dp[2] 又被拆成 dp[1]面额1和 dp[0]面额2于是“12”和“21”都被计入结果偏大。先种类后金额的方式处理完面额 1 之后dp[2] 已经有“两张1”这一种方案再处理面额 2 时dp[3] 从 dp[1] 转移过来而 dp[1] 里只有“一张1”不会再重复回溯出“先2后1”的分支因为面额 2 是最后处理的它不会回头再去组合面额 1 的新排列。这个循环顺序不是玄学而是“组合计数不重不漏”的关键。你可以自己拿两张扑克牌模拟一下先规定好“按面额从小到大考虑每个面额一次全部考虑完”就能保证每种组合只被计算一次。2.4 空间压缩的理解二维到一维的过程中内层金额必须从小到大正序遍历。这一点和 0/1 背包正好相反。0/1 背包内层逆序是为了防止同一件物品被重复使用而完全背包允许无限取用所以内层正序让 dp[j] 可以利用更新后的 dp[j - a[i]]相当于允许当前面额被多次选择。这地方容易记串。我的记忆方法是0/1 背包物品只能用一次内层倒序让更新后的大金额不会被本次循环中的小金额“污染”。完全背包物品能用无数次内层正序让更新后的小金额继续去更新大金额实现“一张一张地叠加”。在方案数问题上正序配合“外层种类”的约束恰好同时满足了“无限使用”和“不考虑顺序”两个条件。3. 代码实现与手把手解析3.1 核心 C 代码下面这份代码可以直接作为模板注释里写清楚了每一步的含义。#include bits/stdc.h using namespace std; const int MOD 1000000007; const int MAXN 1005; const int MAXM 10005; int a[MAXN]; int dp[MAXM]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, M; cin n M; for (int i 1; i n; i) { cin a[i]; } dp[0] 1; // 凑 0 元什么都不拿 for (int i 1; i n; i) { for (int j a[i]; j M; j) { dp[j] (dp[j] dp[j - a[i]]) % MOD; } } cout dp[M] \n; return 0; }3.2 每一步的意图解释首先用ios::sync_with_stdio(false); cin.tie(0);关掉流同步。M 最大一万左右其实不关也能过但这是竞赛习惯留着没坏处。然后读入纸币种类数和目标金额。注意这里我叫它 M题目里可能用 m 或 other 变量名看题面命名避免跟数组名冲突。dp 数组开多大我习惯开成MAXM比 M 最大值再大几十防止边界访问越界。你也可以用 vector 动态分配但静态数组更快更稳。初始化dp[0] 1含义是一个空组合。很多初学者把 dp 数组初始化为 0然后发现 dp[M] 永远是 0就是因为少了这一步。为什么不把 dp[0] 设成 0从状态定义看凑 0 元确实只有“一张都不拿”这一种方案所以是 1。从转移推导看如果没有这一项所有 dp[j] 在第一次处理面额时都由 dp[0] 起步这一项缺失等于整个转移链断掉。接下来两层循环。外层 i 表示“当前正在考虑第 i 种面额”内层 j 从 a[i] 到 M。内层起点设为 a[i] 是因为 j a[i] 时不可能使用当前面额直接跳过属于小优化。更新时取模。如果不用模dp 在 M 较小时可能不爆但题目明确要求取模所以每加一次就取一次模安全。也可以写成dp[j] dp[j - a[i]]; if (dp[j] MOD) dp[j] - MOD;因为加法最多两个小于 MOD 的数相加不会超过 2e914用 int 也可能溢出int 上限约 2.147e9所以要么用 long long要么用上面的减法取模。我给出的(dp[j] dp[j-a[i]]) % MOD会先做 int 加法可能溢出在某些环境下会出错。所以更稳妥的写法是dp[j] (1LL * dp[j] dp[j - a[i]]) % MOD;强制转 long long 再做模或者干脆把 dp 数组声明成long long。这是很多人在数值范围上踩的隐性坑后面会详细说。3.3 一个小优化内层起点能不能更小如果当前面额 a[i] 很大比如 10000而 M 只有 10000内层循环只执行一次无所谓。但如果面额五花八门可以考虑跳过无用的面额如果 a[i] M这张纸永远用不上直接 continue。不过这属于锦上添花不影响正确性。3.4 用 Python 写同样逻辑更直观很多新手用 Python 刷题我也顺带给出等价写法MOD 10**9 7 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(x, M 1): dp[j] (dp[j] dp[j - x]) % MOD print(dp[M])这个写法逻辑一模一样只是语言层面的区别。Python 的列表索引和切片天然适合这种循环但需要注意 Python 的取模在数值较大时稍微慢一点本题的数据范围完全没问题。3.5 与标准完全背包最大价值的对比如果你已经会了完全背包模板for i 1 to n: for j a[i] to M: dp[j] max(dp[j], dp[j - a[i]] v[i])你会发现计数版本仅仅是把max换成把初始化的dp[0]0换成dp[0]1。这个相似性不是巧合而是同一个状态定义下的两种度量一个是“价值最大”一个是“方案总数”。理解这一点后你以后遇到“最少张数”“最多方案数”“能否凑成”都能在同一套框架里快速迁移。4. 常见问题与排查技巧实录4.1 内层循环顺序写反结果比样例大这是最经典的错误。面额 1、2凑 3正确结果应该是 2 种111 和 12如果写成先金额后面额会算出 3 种多一个 21。排查方法非常简单打表输出 dp[0..M]看中间过程。我一般会在出问题时加一段调试代码for (int j 0; j M; j) { cerr dp[j] ; } cerr \n;观察 dp[2] 在处理完面额 1 之后的值以及处理完面额 2 之后的值。如果发现 dp 的增长轨迹有“回头”的迹象基本就是循环顺序错了。4.2 模数取错或忘记取模题目如果要求模 1e97你取模时写成 1000000007 没错但有人会把模数写成 1000000009或者 998244353这个是题目里给定的照着来。忘记取模的话M 到 10000、面额多时方案数会呈指数级膨胀long long 都扛不住最后 WA 或者 RE溢出后变负数。稳妥做法是 dp 数组直接用 long long每处更新用(dp[j] dp[j - a[i]]) % MOD输出时再转 int 也没问题。4.3 面额列表里有重复值需要去重吗这是个很值得聊的隐蔽点。假如两种不同纸币面额相同比如两种 5 元面额题目把它们算作不同种类还是同一种看题面描述。如果它说“n 种纸币面值为 a[i]”通常意味着这 n 个值本身可能不同但如果输入出现两个相同的 a[i]按常理这是一模一样的两种纸币组合数不应该因此增多。不过很多出题人不会故意塞重复面额给你添乱。如果你不放心可以先排序去重sort(a 1, a n 1); int cnt unique(a 1, a n 1) - (a 1); n cnt;这样保证了每种面额只考虑一次逻辑更严谨。但注意如果题目把“种类”定义为不同编号哪怕面额相同也算不同种那就不能随便去重。出题人一般不会搞这种反直觉设定请以原题面为准。4.4 金额 M 很大dp 数组开不下怎么办如果 M 上亿二维肯定不可能一维数组也吃紧。这种时候要看是不是要改成其他算法比如生成函数、离散化、数论优化等。但 P2840 的数据范围就是给一维 DP 用的不必自己吓自己。4.5 遇到“多组输入”的情况有些题会重复输入多组 n 和 M。如果题目要求多组数据务必记得每组重新初始化 dp 数组尤其是 dp[0] 重新置 1其余位置清零。用memset(dp, 0, sizeof(dp));或者fill(dp, dp M 1, 0);都行别留着上一组的数据。4.6 方案数很大答案全 0如果你输出的 dp[M] 一直是 0先检查输入有没有读对。然后检查 dp[0] 是否初始化为 1。我给一个真实案例有个朋友把 dp[0] 初始化成 0理由是“0 元不用凑所以是 0 种方案”。这个理解看似合理但转移全靠 dp[0] 起步一旦它是 0整个车厢就没法动了。把 dp[0] 理解成“从起点出发的基准状态”更容易接受它代表一种空集组合。4.7 把“每种纸币无限张”理解成“每种只能选一次”如果用 0/1 背包的方式去解即内层循环倒序你会得到一个错误但又不是完全离谱的答案每种纸币最多用一次。当面额列表里有 1 和 2凑 3 时0/1 背包会得到 0 种方案因为 12 允许但 1 被用过就不能再用2 也用完不可能凑出 3除非再来一张 1。答案明显不对。记住 P2840 是“无限张”必须完全背包正序。5. 从一道题看开去这题背后的知识体系5.1 完全背包“计数”在竞赛中的变形等你 AC 了 P2840把目光放大一点这类题会延伸出很多花式考法。纸币问题 3每种纸币有数量上限这时内层要多加一层枚举张数或者用二进制拆分 0/1 背包。硬币找零问凑出 M 的最小硬币数把换回min。方案数带限制比如不能使用某种面额或至少使用某种面额本质是对状态做单点禁用或偏移。高精度下的大数方案数M 不大但结果超过 64 位可能要求用高精度或 BigInt这时思路不变只是实现麻烦。因此P2840 的价值不是让你背一道代码而是让你彻底理解“计数 DP 的顺序与状态设计之间的关系”。以后见到“不同方案”“方案总数”“mod x”这些字样第一反应就该想到计数背包而不再是暴力搜索。5.2 动态规划中的“无后效性”在这道题里如何体现题目里每种面额可以无限选但我们在设计状态时并没有记录“当前还剩下哪些面额可用”因为我们规定只按面额种类顺序推进。当外层循环走到第 i 种面额时未来只会使用第 i 种以及后面的面额不会回头去用第 i-1 种。这就是无后效性当前状态 dp[j] 已经包含了“前 i-1 种面额的全部方案”之后转移不再关心具体是哪些组合达成的只关心金额 j 本身。这种“只关心当前不管历史”的视角是所有 DP 进阶的基石。你如果能把这一步想透后续区间 DP、树上 DP、状压 DP 都能顺很多。5.3 如何验证你的 DP 是否正确除了提交 AC自己也要学会验证。小数据可以直接手算或者暴力枚举验证。比如现有一个 n3, M100 的测试你可以用递归枚举出所有组合数再和 DP 结果对拍。对拍是竞赛里最直接的信心来源。一个简单的验证思路面额只有 5 和 10凑 100。因为 5 可以凑所有 5 的倍数组合方式无非是“用多少张 10 剩余的用 5 补”所以方案数是 110 张 10、1 张 10、...、10 张 10。你用上面的代码跑一下看是不是 11。如果不是说明某个环节还没吃透。6. 实操中的几点个人体会6.1 写计数 DP 时要“慢”不要急AC 率高的选手面对这类题往往不是靠手速而是靠严格的步骤先确认“方案”的语义再定状态再写转移最后才写代码。我见过很多人大脑里还没分清“组合”和“排列”就开始敲循环结果调试时间反而比认真想一分钟更久。6.2 建议自己造几组极小的测试数据不要只依赖样例。我常用的一组手工测试输入只有一种面额 3M6那么方案数只有 1 种两张 3 元因为不存在其他面额也不能用别的组合。输入面额 1 和 3M3方案数是 2 种三张 1 元一张 3 元。输入面额 2 和 4M5方案数是 0 种因为 5 凑不出来。这些极限数据能快速暴露你初始化和循环方向的错误。6.3 把“滚动数组”的更新顺序画成图拿张纸写下 dp[0] 到 dp[M]然后用箭头标出每个 dp[j] 从哪个位置转移过来。处理完一种面额后再画一次。你会发现正序循环的箭头始终向右延伸而每一种面额只会在自己的“层”内更新。这张图比看十遍代码都更有用。6.4 关于取模的写法我最终选择 long long实际刷题时我喜欢把 dp 数组定义成 long long更新直接写dp[j] dp[j - a[i]]; if (dp[j] MOD) dp[j] - MOD;因为 dp[j] 和 dp[j - a[i]] 都小于 MOD加完小于 2 * MOD减一次就够了既快又稳。如果怕减一次不够可以用 while但这里是够的。这个写法在 OI 中很常见建议记住。6.5 什么时候用“二维数组”更安全如果你刚开始学还没彻底掌握滚动数组的循环顺序我建议先写二维版本保证正确AC 之后再改一维。二维状态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]; // 不选第 i 种 if (j a[i]) { dp[i][j] dp[i][j - a[i]]; // 至少选一张第 i 种 } } }注意这里“至少选一张第 i 种”用的是同一层的 dp[i][j - a[i]]而不是 dp[i-1][j - a[i]]。这个转移的背后逻辑是我们允许当前面额连续用多次所以要从“已经选了当前面额”的状态再叠加。这个写法和“多重背包”区分开来是完全背包二维形式的精髓。二维的好处是转移语义直白不怕循环顺序写错。缺点是空间 O(n * M)在 n1000、M10000 时是 1000 万long long 要 80MB可能超内存。所以竞赛里最终还是推荐一维滚动数组。6.6 别忽视“无解”情况如果所有面额的最大公约数不整除 M那必然凑不出 M方案数为 0。DP 不会出错它会自然输出 0。只是要理解不是所有金额都能被任意凑出这也解释了为什么用 GCD 可以提前预判一些极端大数据。不过 P2840 里你不用特意写判断DP 自然会处理。7. 写在最后的经验之谈做这道题时我自己最初也犯过“先金额后种类”的错误当时 debug 了很久最后输出错误结果让我百思不得其解。后来我把“组合”和“排列”这两个概念在纸面上反复推演才意识到顺序的意义。从那之后我养成了习惯任何计数 DP 题第一步先问“方案的定义是否区分顺序”再决定循环结构。这个习惯帮我避开了无数后续的坑。另外如果你准备打比赛推荐把 P2840 作为“完全背包计数”的基准模板把它和 0/1 背包计数、多重背包计数放在一起对比学习。三种背包的代码只有微小差别但背后的数学模型完全不同。熟练之后你遇到“兑换零钱”“邮票组合”这类问题基本一眼就能拆解出状态设计。最后再分享一个小技巧遇到这类题先写一个递归暴搜验证函数再写 DP用随机小数据对拍一遍放心程度直接翻倍。特别是当你修改了循环顺序、取模策略后对拍能让你少提交好几次 WA。我的经验是宁可多花三分钟对拍也不要在评测记录里浪费几个罚时。