洛谷 P2840 纸币问题 2题面一句话有 n 种面值的纸币每种纸币都有无限张问凑出总额 m 元一共有多少种不同的付款方案答案对 1000000007 取模。第一次看到这题很多人的反应是这不就是完全背包套模板吗然后很快写完交上去WA。我也曾是这样的人。反复对拍后发现问题几乎总是出在“循环方向”和“状态语义”上。这篇文章不打算只贴代码而是把从问题抽象、状态设计、循环顺序到取模细节整条链路讲透也顺带聊聊这道题能延伸到哪几类变体。如果你刚学 DP 不久或者刷了十几道背包题但一遇到“计数类”就发懵这篇应该对你有用。1. 先把题面翻译成老朋友完全背包计数模型1.1 无限张纸币到底改变了什么不少人看到“无限张”第一反应是拿着某种面值的纸币我可以选 0 张、1 张、2 张……一直选到面值超过总额为止。如果真这么暴力枚举光是处理一种纸币就要循环 O(m / w) 次n 种纸币叠上去总复杂度能到 O(n × m^2)稍微大一点的数据直接跑不动。这时候必须想到背包模型。把面值看成物品的体积把总额 m 看成背包容量纸币“无限张”就是典型的完全背包。区别只在于普通完全背包要最大化价值这里没有价值的概念我们只关心“有多少种方式恰好装满容量 m”。状态的定义和转移逻辑就得围绕“计数”来重写而不是硬套以前最大价值的模板。用小学枚举来感受一下题目假设有 1 元、2 元、3 元三种纸币各无限张凑 4 元有几种手写一下11112112231一共 4 种。这个答案先摆在一边后面我会用它来校验 DP 表到底对不对。1.2 “方案数”不是“张数”也不是“排列数”这里有一个特别容易踩的坑题目要的方案数到底是组合数还是排列数举个例子“用 1 元和 2 元凑 3 元”按组合来算只有 2 种21、111。但如果按排列来算12 和 21 会被当成两种不同方案结果就变成 3 种。纸币问题 2 的常规题意是“有多少种付款方式”这里面隐含了“哪几种面值分别用了多少张”顺序无关。也就是说2 元 1 元和 1 元 2 元是同一种付款方案。这个区分直接决定了后面两层循环谁是外层、谁是内层。很多人没想明白甚至没意识到这个区别等到换一道“爬楼梯每次跨 1 或 2 步”的题又把完全背包的循环顺序套进去结果错得莫名其妙。所以读题时但凡出现“第 i 种纸币”这种说法基本就是在按币种分组组合计数优先。2. 状态定义与转移方程把“不重不漏”四个字落到实处2.1 dp[j] 的确切含义定义 dp[j] 表示“凑出 j 元钱的方案数”。一开始我们没考虑任何纸币只能凑出 0 元方案数是 1也就是什么都不选所以 dp[0] 1。其他 dp[j] 初始为 0表示暂时凑不出来。很多初学背包的人会把 dp[0] 也初始化成 0这个错误极其常见而且样例往往看不出问题因为有些数据碰巧不影响最终结果但一旦出现“什么都不选”这条路径被需要的情况答案就会少算。记住一句话在计数类背包里dp[0] 1 是边界它的含义是不选任何纸币就凑出 0 元这是一种合法方案。空间上我们不需要真开一个二维数组 dp[i][j] 来记录“前 i 种纸币”的状态直接在原数组上滚动更新就行。滚动之后 dp[j] 的语义变成了“处理完当前这轮纸币之后凑出 j 元的方案数”理解这一点对解释循环顺序很关键。2.2 加入一种面值后转移为什么是累加每当我们把面值 w 的纸币纳入考虑dp[j] 的更新逻辑是新的凑法 原来的凑法完全不用 w 用了至少一张 w 的凑法。后者怎么算我们往“凑出 j - w 元的方法”里再塞一张 w 元纸币。关键是dp[j - w] 里已经包含了继续使用 w 的可能因为内层循环正序扫描时会不断把新方案累加回去。这样一层一层叠就实现了“无限张”的效果而不需要真的写一个 for 枚举用了多少张。转移方程写成公式就是这样dp[j] (dp[j] dp[j - w]) % MOD其中 j 从 w 扫到 m。注意这个加号。它是累加不是赋值。赋值是把旧方案直接覆盖累加才是把“不用 w 的方案”和“用 w 的方案”合并起来。理解到这一层比记住代码重要得多。2.3 手工模拟n3, m4, 面值 1, 2, 3我只信手算。咱们把前面那个“1 元、2 元、3 元凑 4 元”的例子完整的 DP 表列出来看看每一步数组怎么变。初始 dp [1, 0, 0, 0, 0]。处理面值 1j 从 1 到 4j1dp[1] dp[1] dp[0] 1j2dp[2] dp[2] dp[1] 1j3dp[3] dp[3] dp[2] 1j4dp[4] dp[4] dp[3] 1此时 dp [1, 1, 1, 1, 1]表示只用 1 元纸币任何不超过 4 的金额都只有一种凑法。处理面值 2j 从 2 到 4j2dp[2] 1 dp[0] 2表示 2 元有两种11、2j3dp[3] 1 dp[1] 2表示 3 元有两种111、21j4dp[4] 1 dp[2] 3这里 dp[2] 已经是 2所以得到三种1111、211、22此时 dp [1, 1, 2, 2, 3]。处理面值 3j 从 3 到 4j3dp[3] 2 dp[0] 3新增 3 元纸币本身j4dp[4] 3 dp[1] 4新增 31最终 dp [1, 1, 2, 3, 4]答案 dp[4] 4和手写枚举完全一致。这一步一定要自己动手演算一遍。看十篇题解不如自己填一次表填完你就会发现dp 数组其实在用一种很优雅的方式把组合方案“按币种字典序”统计了一遍既没有漏也没有重。3. 循环顺序才是这道题的命门正序还是倒序3.1 正序循环如何做到“一张纸币用多次”完全背包和 01 背包在代码上只有一个区别内层循环 j 是正序还是倒序。但就这一个字母决定了天壤之别。01 背包每种物品只有一件内层 j 从 m 倒序扫到 w是防止同一件物品被重复放入。倒序时dp[j - w] 还是“上一轮”的状态还没被当前物品更新过所以每个物品最多被用一次。完全背包纸币无限我们希望同一种面值可以被反复计入选方案因此内层 j 从 w 正序扫到 m。正序时dp[j - w] 可能已经被当前这轮面值更新过了意味着“当前面值我已经在凑 j - w 时又用过一次”再加上当前这一张自然就实现了多次使用。用一个生活化的类比倒序就像每个人手里只有一张票进场时验过就作废所以没人能玩两次正序就像游乐场的通票你用完之后还能回到入口再排一次队想玩几次玩几次完全背包就是这种“通票”机制。3.2 如果我手滑写成了倒序会发生什么别急着觉得“倒序就是错”咱们用数据说话。还是 n2m3面值 1 和 2。正确正序跑出来是 2 种111、21。这个结果前面推过。写错成倒序会怎样内层 j 从 m 倒到 w处理面值 1j 从 3 到 1j3dp[3] dp[3] dp[2] 0j2dp[2] dp[2] dp[1] 0j1dp[1] dp[1] dp[0] 1这一步 dp [1, 1, 0, 0]注意 dp[2] 和 dp[3] 还是 0因为 1 元纸币被当成“只能用一次”根本无法连续用三张凑出 3 元。处理面值 2j 从 3 到 2j3dp[3] dp[3] dp[1] 0 1 1j2dp[2] dp[2] dp[0] 0 1 1最终 dp[3] 1只算出了 21 这一种漏掉了 111。问题出得很明显倒序把每种纸币都当成了独立的限量单品完全违背了“无限张”的题意。这种错误在笔试里特别隐蔽因为小样例往往能过比如面值恰好只有一种、或者 m 很小都可能碰巧遮住问题。一旦数据变大方案数偏少的 bug 就集中暴露。我自己当年就干过这事把完全背包计数套进 01 背包的模板里样例过了还沾沾自喜结果大数据 WA 得话都说不出来。从那以后我每次写完背包都会盯着 for j 的循环方向盯三秒钟确认自己这次是“无限供应”还是“限量供应”。3.3 两层循环交换会怎样再谈排列与组合还有一种容易混淆的写法外层循环金额内层循环面值。这写出来的不是组合方案数而是排列方案数。同样用面值 1、2 凑 3 元来试。外层 j 从 1 到 3内层遍历面值j1处理面值 1dp[1] 1j2处理面值 1dp[2] dp[1] 1处理面值 2dp[2] dp[0] 1dp[2] 2j3处理面值 1dp[3] dp[2] 2处理面值 2dp[3] dp[1] 1dp[3] 3结果 3。这里的 3 正好对应三种排列111、12、21。21 和 12 被拆成了不同方案。纸币问题 2 按题意要的是组合数所以正确写法必须是外层币种、内层金额并且金额正序。如果你以后遇到“上楼梯”问题或者题目明确说“不同的支付顺序算不同方案”那时候才需要把两层循环颠倒过来。判断标准很简单题目里强调的是“几种面值的组合”还是“支付的先后次序”。这题是前者。4. 完整实现与模运算里的那些坑4.1 一份能直接 AC 的 C 代码代码不长核心就是两层循环加取模。下面这段是我个人习惯的写法注释写得很细方便直接对着理解。#include bits/stdc.h using namespace std; const long long MOD 1000000007LL; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorlong long dp(m 1, 0); dp[0] 1; // 凑 0 元有一种方案什么都不选 for (int i 0; i n; i) { int w; cin w; // 完全背包计数j 正序从 w 到 m for (int j w; j m; j) { dp[j] (dp[j] dp[j - w]) % MOD; } } cout dp[m] \n; return 0; }结构非常简单。但越是简单的代码越容易在细节上翻车。下面几个点是我反复踩过的。4.2 取模的时机与 int/long long 的边界加法取模要放在每次累加之后而不是最后统一取模。原因很简单不取模的话dp[j] 的值会随着循环次数指数级上涨早早就溢出 long long 了。边加边模能保证 dp 数组每个元素始终落在 [0, MOD) 的范围内后续计算安全性高得多。这里有个比较冷门的细节MOD 取 1000000007 时两个小于 MOD 的数相加最大约为 2000000014这个值恰好小于 int 的最大值 2147483647所以用 int 数组勉强不会溢出。但如果你换一道题模数改成了 1000000009两倍就超过 int 上限了。与其每次算边界不如直接用 long long写起来省心也不用担心哪天换个模数或者题目加强数据就把自己坑了。有人可能觉得 dp[j] (dp[j] dp[j - w]) % MOD 多了一次取模运算会不会变慢完全不用担心这个量级的操作在 O(n × m) 面前不值一提。稳定性比那点微秒级性能重要得多。4.3 复杂度分析与数据范围判断时间复杂度 O(n × m)空间复杂度 O(m)其中 n 是纸币种类数m 是目标总额。如果 m 在 10^5 级别空间占用大概不到 1MB时间也完全没问题。如果 m 到了 10^6 级别dp 数组用 long long 约 8MB普通 OJ 也扛得住。真正需要警惕的是 m 达到 10^9 甚至更大的情况这时候普通 DP 已经不是空间够不够的问题而是时间上根本跑不完需要换思路这一点下一章会专门讲。另外虽然这题输入时面值 w 大于 m 的纸币对凑钱毫无帮助但不需要特判跳过。循环 j 从 w 到 m如果 w m循环体一次都不会执行自然被忽略了。代码保持简单就好。4.4 面值输入顺序、重复面值的处理输入面值可能并不是有序的这不影响正确性。因为外循环的每一轮只是“把某一种面值加入可用集合”加入顺序不影响最终的组合集合。你可以先处理 3 元再处理 1 元得到的 dp[m] 还是一样。如果输入里出现了重复面值比如两个 1 元那它们在题目语义里是两种不同的纸币种类DP 会如实把它们当成两种币种处理方案数会相应增加。这不是 bug是符合题意的。如果你明确知道面值重复会让题目失去意义那多半是题面保证了互不相同或者你该去读原题确认而不是在代码里强行去重。5. 别再只会背模板三道变体题帮你彻底内化5.1 纸币问题 1把计数改成可行性判断如果题目从“有多少种方案”改成“能否凑出 m 元”模型不变只是把 dp 数组从计数改成布尔判断。初始化 dp[0] true其他为 false。转移时 dp[j] dp[j] || dp[j - w]。循环顺序仍然是完全背包那套外层币种内层金额正序。时间复杂度一样但是不用取模了写起来更轻量。这类题存在的意义是帮你识别同一个背包骨架赋值代表“决策”累加代表“计数”或运算代表“可行性”。三者代码结构几乎一样但状态语义完全不同。无脑背模板的人一旦遇到这种微调就会露怯。5.2 每种纸币有数量限制多重背包计数多了“第 i 种最多用 c_i 张”的限制问题就变成了多重背包计数。可以先把 c_i 拆成 1、2、4、…… 这样的二进制组每组当做一个 01 背包物品来跑计数也可以直接在最内层枚举当前面值用 k 张写成for j from w to m: for k from 1 to min(c[i], j / w): dp[j] dp[j - k * w]这种写法直观但复杂度高数据大了需要单调队列优化。如果你只是想搞懂 P2840先不用深入多重背包的优化但至少要知道完全背包的“无限”一旦改成“有限”循环方向就未必还是简单正序得回到“组内有限选择”的思路上来。5.3 要求输出具体方案怎么改如果题目还要求输出任意一种凑法处理方式是在 DP 的同时记录转移来源。每次 dp[j] 因为 dp[j - w] 被累加时就把来源记录成一个 pre 数组比如 pre[j] w表示凑出 j 元的方案里有一张面值 w。最后从 m 开始不断用 pre[m] 反推得到一个面值序列。注意这只能输出一种方案。如果你想输出所有方案那已经不是背包题而是需要 DFS 回溯穷举了复杂度会指数级增长。5.4 如果 m 特别大比如 10^18怎么办这是我自己刷题时最深刻的体会之一任何 DP 模板都有边界。当 m 大到普通数组根本开不下O(n × m) 的时间也完全不可接受时需要换工具。如果 n 很小比如只有两三种面值可以尝试把问题建模成线性递推然后用矩阵快速幂在 O(n^3 log m) 的时间内求解。如果 n 和 m 都很大生成函数或某些数学技巧可能更有用但那就超出本文范围了。遇到这种题没必要慌先看数据范围再决定用哪把钥匙。P2840 作为经典题设计初衷就是让你吃透完全背包计数这一套所以 m 一定在普通 DP 能解决的范围内。把基础模型的循环逻辑、状态语义练到肌肉记忆再去看那些高级优化才不会空中楼阁。我个人在实际操作中的体会是这题最值得花时间的不是 AC 的那一下而是静下心把 dp 表从头到尾手推一遍。尤其是第 3 章那个 1 元、2 元凑 3 元的正序倒序对比推完你就彻底明白“无限张”到底是怎么通过循环方向表达出来的。以后遇到再花哨的背包变体第一件事永远是问自己物品是无限的还是有限的我要的是方案数还是可行性顺序算不算不同方案三个问题答完状态转移和循环方向基本就水落石出了。