企业官网建设流程全解析

第一次在题目列表里看到“Sewing Buttons with Grandma”（UVa 12316）时，我以为是那种讲故事送温暖的题。读完题面发现，这题翻译过来就是：奶奶有一堆大小不一的纽扣，每一种都有无限多颗，她想凑出一个指定大小的总和，问一共有几种凑法。没有感情戏，没有场景描写，剩下的全是背包问题。得，祖母再慈祥，该写状态转移还是得写。

这题在很多算法爱好者看来是入门级别的完全背包计数题，但它有一个很容易被人忽略的坑：同样是“用无限物品凑总和”，循环顺序写错，答案就会从组合数变成排列数，WA得毫无脾气。再加上答案可能特别大，很多语言自带大数，但C++选手就得自己手写。这篇文章我会把这道题从读题、建模、状态设计、去重技巧、大数加法到踩坑经验全部过一遍，适合正在刷动态规划基础题、尤其是背包专题的同学参考。

1. 题目到底在做什么：先把这个“缝扣子”问题翻译成数学题

1.1 题面看着温馨，条件其实很硬

题目背景很简单：奶奶要缝一件有很多扣眼的外套，身边有一个装满纽扣的盒子。盒子里有若干种尺寸的纽扣，每一种都不限数量。现在给定一个目标大小 n，问用这些纽扣能凑出多少种不同的方案，使得所选纽扣的尺寸总和恰好等于 n。

比如目标大小是 5，纽扣种类有两种：尺寸 2 和尺寸 3。那么可以凑出的方案只有一种：2+3。虽然你写代码时可能是先取 2 再取 3，也可能先取 3 再取 2，但“拿一颗 2 和一颗 3”这件事在物理世界里是同一个结果，不能当成两种方案。这就是这道题和很多初学者的直觉最容易打架的地方。

题目的输出是一串数字，不是取模后的余数。也就是说，方案数可能非常大，甚至超出 64 位整数能表示的范围。这个细节直接决定了我们后面必须处理大数。很多人在状态转移都写对的情况下栽在这一步，觉得“可能很大”就是“可能超过 int”，结果用 long long 一交，直接溢出，输出一堆乱码。

1.2 输入输出和数据范围

题目是多组输入，常见写法是读到文件末尾结束。每一组数据先给一个正整数 n，表示需要凑出的目标大小；接着给一个正整数 m，表示纽扣的种类数；然后给 m 个整数，表示每种纽扣的尺寸。

[ n \le 100,\quad m \le 50 ]

这是题目中隐藏的关键信息。n 只有 100，说明我们完全可以开一个长度为 n+1 的 dp 数组，不需要任何高级优化。m 也只有 50，循环嵌套没有任何压力。真正的压力全在结果数字的长度上，因为组合方案数是指数级别的，哪怕 n 很小，方案数也可能长到几十位甚至上百位。

有些版本的题目会把 n 为 0 作为终止条件，有些版本不会，具体以你复现时的题面为准。我下面给出的代码按“读到 EOF，遇到 n=0 就结束”的常见风格处理，如果没有这个约定，删掉 break 分支即可。

1.3 为什么直接判定为完全背包计数问题

判断一个题是不是背包问题，就看三个要素：物品、容量、选择限制。这里的物品是纽扣种类，容量是目标大小 n，限制是每种纽扣可以取任意多颗。所以模型非常清晰：完全背包，但不是求最大价值，而是求方案总数。

这里最容易出现的一个误区是：“这不就是组合数学里的正整数拆分吗，能不能用生成函数、母函数去解？”理论上可以，生成函数的系数就是答案，但写起来比动态规划复杂，而且在大数场景下没有任何优势。对 OJ 来说，动态规划就是最标准、最稳妥、最好写的解法。

还有一点值得提醒：有些同学第一眼看到“无限取”就想到高中数学里的隔板法、整数拆分公式，但库里尺寸不是从 1 到 n 的连续整数，而是给定的任意正整数序列。比如可能只有尺寸 3 和尺寸 5，没有 1 和 2。这种情况下整数拆分公式完全不适用，必须老老实实用背包。

2. 解题思路拆解：从暴力枚举到动态规划

2.1 暴力枚举为什么活不过两秒

最朴素的想法是枚举每种纽扣取多少颗。设第 i 种纽扣取了 (c_i) 颗，那么要满足

[ \sum_{i=1}^{m} c_i \times w_i = n ]

这个枚举的规模有多大？最坏情况下，每一种纽扣的取值都有 (O(n / w_i)) 种可能，全部组合起来是乘积级别。n=100，m=50 时，即使每种尺寸都比较大，暴力组合也会轻松爆炸。就算剪枝，枚举过程中还涉及“判断是否重复”的问题，因为纽扣组合不区分顺序，枚举生成的有序组合还要再做一次去重，复杂度根本不可接受。

所以这题必须用动态规划。动态规划的好处是，它把“用前 i 种纽扣凑某个总和”这件事做成状态，通过递推避免重复计算，同时天然规避了顺序问题。

2.2 状态定义：让“前 i 种”成为核心维度

定义状态：

[ dp[i][j] = 前 i 种纽扣凑出总大小 j 的方案数 ]

其中 i 从 0 到 m，j 从 0 到 n。这里“前 i 种”是严格有序的：我们先把所有纽扣种类从左到右排好队，考虑前 1 种、前 2 种……这样在计算时，方案集合被一张“种类先后”的标签隔离，永远不会把同一种组合通过不同顺序重复计入。

初始化也很直观：前 0 种纽扣凑出总大小 0 的方案数是 1，也就是什么都不取；前 0 种纽扣凑出任何大于 0 的总大小都是 0，因为没有任何纽扣可用。

[ dp[0][0] = 1 ]

[ dp[0][j] = 0 \quad (j > 0) ]

2.3 转移方程：选 0 个和至少选 1 个

有了状态，怎么从前面的状态推到当前状态？对第 i 种纽扣（尺寸为 w），我们有两种情况的叠加。

第一，完全不使用第 i 种纽扣。那么方案就是从“前 i-1 种”凑出 j：

[ dp[i][j] += dp[i-1][j] ]

第二，至少使用 1 颗第 i 种纽扣。可以先拿掉一颗尺寸为 w 的纽扣，剩下的 j-w 仍然允许继续使用第 i 种，因为数量无限：

[ dp[i][j] += dp[i][j-w] \quad (j \ge w) ]

这里需要仔细体会：为什么是 (dp[i][j-w]) 而不是 (dp[i-1][j-w])？因为当我们“已经决定至少放一颗第 i 种纽扣”时，剩余的 j-w 还可以再放第 i 种纽扣，这是一种递归式的定义。如果写成 (dp[i-1][j-w])，就只能放一颗第 i 种纽扣，第二颗、第三颗都放不了，那就退化成 0/1 背包了。

完整的转移就是：

[ dp[i][j] = dp[i-1][j] + (j \ge w \text{ 时 } dp[i][j-w]) ]

这个写法我在刚开始学的时候总觉得有点绕，后来用一个生活例子理解：你在自助餐厅拿菜，面前有“前 i 道菜”的取餐区。要么这一轮完全跳过第 i 道菜，那么方案数继承“前 i-1 道菜”的情况；要么你至少夹一筷子第 i 道菜，夹完之后你还可以接着夹这道菜，于是问题回到“前 i 道菜”里凑 j-w 的剩余量。这样就既允许无限取，又因为没有给第 i 道菜设置“排列顺序”，不会把同一道菜的不同夹取顺序重复计数。

2.4 一维压缩：从二维表到滚动数组

观察转移式，(dp[i][j]) 只依赖 (dp[i-1][j]) 和 (dp[i][j-w])。前者是上一行的旧值，后者是本行前面位置刚算出来的新值。所以我们可以只用一个一维数组，按顺序覆盖更新。

[ dp[j] = dp[j] + dp[j-w] \quad (j \text{ 从小到大遍历}) ]

这里的内层循环顺序非常关键：必须从小到大遍历 j。因为 (dp[j-w]) 在 (j) 之前已经被更新过，它代表的正是同一轮内“已经使用了第 i 种纽扣”的方案数，这正好对应完全背包“允许无限使用”的特性。如果改成从大到小遍历，(dp[j-w]) 还是上一轮的旧值，那就变成 0/1 背包，每种纽扣最多用一次。

这个“正序还是倒序”的细节，是背包问题里的老演员了，但每次考试还是有人错。我的习惯是记一句话：完全背包正序，0/1 背包倒序。做题前先想清楚这题是无限取还是一次取，再决定方向。

3. 代码实现与关键细节：大数、初始化、循环顺序

3.1 大数加法：自己动手，不用库

先回答一个问题：这题的方案数到底能有多大？n=100、m=50、所有纽扣尺寸都是 1 时，答案是 (2^{99}) 级别的天文数字，大约 30 位十进制数。如果尺寸更小、种类更多，还能更大。long long 只能存到 (9.22 \times 10^{18})，连零头都不够，所以必须用大数。

C++ 在 ACM 环境下最稳妥的做法是自己写一个字符串加法。加法逻辑不难，按位从低位到高位加，处理进位。写一次通用函数，后面所有类似“计数型背包”的题都能直接用。这里我给出一个可靠实现版本：

string addString(const string& a, const string& b) { string res; int i = (int)a.size() - 1; int j = (int)b.size() - 1; int carry = 0; while (i >= 0 || j >= 0 || carry) { int sum = carry; if (i >= 0) sum += a[i--] - '0'; if (j >= 0) sum += b[j--] - '0'; carry = sum / 10; res.push_back(char('0' + sum % 10)); } reverse(res.begin(), res.end()); return res; }

这个函数每次生成一个新的字符串，虽然会有额外开销，但在 n≤100 的场景下完全足够。如果你担心多次分配字符串导致超时，也可以用固定长度的 char 数组配合手写进位，但一般情况下没必要。

3.2 C++ 参考实现

下面给出一个可以直接 AC 的完整实现。为了节省空间，dp 数组直接开一维，并且用 string 类型存储大数。

首先初始化 dp 数组为全 "0"，再把 dp[0] 设置为 "1"，表示凑出大小为 0 的方案有一种。然后外层循环枚举纽扣种类，内层循环用正序更新 dp。最终 dp[n] 就是答案。

#include <bits/stdc++.h> using namespace std; string addString(const string& a, const string& b) { string res; int i = (int)a.size() - 1; int j = (int)b.size() - 1; int carry = 0; while (i >= 0 || j >= 0 || carry) { int sum = carry; if (i >= 0) sum += a[i--] - '0'; if (j >= 0) sum += b[j--] - '0'; carry = sum / 10; res.push_back(char('0' + sum % 10)); } reverse(res.begin(), res.end()); return res; } int main() { int n; while (cin >> n && n) { int m; cin >> m; vector<int> w(m); for (int i = 0; i < m; i++) { cin >> w[i]; } vector<string> dp(n + 1, "0"); dp[0] = "1"; for (int i = 0; i < m; i++) { for (int j = w[i]; j <= n; j++) { dp[j] = addString(dp[j], dp[j - w[i]]); } } cout << dp[n] << "\n"; } return 0; }

这段代码里最需要注意的就是for (int j = w[i]; j <= n; j++)，内层从 w[i] 开始，从小到大走到 n。很多人在写完全背包求方案数时，习惯用二维数组，然后手动写三重循环枚举第 i 种取 k 个，那样也能过，但代码更长，也更难查错。一维写法干净利落，前提是理解清楚“正序更新”的含义。

3.3 Python 对照：享受语言红利，但也别掉坑

如果你平时刷题用 Python，那大数问题直接消失，因为 Python 的整数没有位数限制。同样的逻辑翻译成 Python：

while True: try: n = int(input()) if n == 0: break m = int(input()) weights = list(map(int, input().split())) dp = [0] * (n + 1) dp[0] = 1 for w in weights: for j in range(w, n + 1): dp[j] += dp[j - w] print(dp[n]) except EOFError: break

这段代码非常短，但有两个 Python 特有的坑需要注意。

第一个坑是输入格式。题目可能把 m 个数字放在同一行，也可能每个数字单独一行。上面代码假设同一行用空格分隔全部读完。但如果你用input()一行一行读，遇到每个数字单独一行的情况就会出错。稳妥一点的做法是写一个生成器，不断读取所有剩余输入，再按空白字符切分，这里不展开，但强烈建议在写 UVa 题之前准备好一套稳定的多行输入模板。

第二个坑是循环顺序。Python 里for j in range(w, n + 1)天然就是正序，完全没问题。如果你写代码时习惯性地想“倒序更安全”，反过来写成了range(n, w - 1, -1)，那就变成 0/1 背包了，答案会错得很隐蔽。

3.4 时间和空间复杂度结论

状态数是 (O(mn))，每个状态只做一次大数加法，所以时间复杂度是 (O(mnL))，其中 L 是结果数字的平均长度，字符串加法本身需要 (O(L))。n≤100、m≤50、L 最多几十位，这个复杂度在评测环境下非常轻松。

空间复杂度是 (O(nL))，因为要保存 n+1 个字符串。n 只有 100，就算每个字符串几十位，内存也就是几 KB，完全不紧张。即便把 n 放大到 10000，这个一维字符串数组也仍然可行，因为瓶颈更多是运行时间而不是内存。

4. 问题排查与高分避坑：把考场上的坑提前踩一遍

4.1 组合还是排列：循环顺序引发的“血案”

我在前面反复强调内层循环正序，很多人在本地手动测试几个小样例时觉得自己对了，一交就 WA。看一个具体例子：目标 n=3，纽扣尺寸为 1 和 2。正确答案是多少？手工枚举：{1,1,1}、{1,2}，共 2 种。

用正确的组合循环算：

• 初始化 dp[0] = 1。
• 处理尺寸 1：dp[1] = 1，dp[2] = 1，dp[3] = 1，对应 {1}、{1,1}、{1,1,1}。
• 处理尺寸 2：dp[2] += dp[0]，得到 dp[2] = 2，对应 {1,1} 和 {2}；dp[3] += dp[1]，此时 dp[1] 等于 1，得到 dp[3] = 2，对应 {1,1,1} 和 {1,2}。

最后 dp[3] = 2，正确。

如果把内外层循环对调，也就是先枚举容量 j，再枚举纽扣种类 w，代码会变成：

for (int j = 1; j <= n; j++) { for (int i = 0; i < m; i++) { if (j >= w[i]) dp[j] += dp[j - w[i]]; } }

这样算出来的 dp[3] 等于 3，因为 {1,2} 和 {2,1} 都被统计进去了，多了一个顺序重复。为什么？因为外层容量、内层物品时，dp[j - w[i]] 会不断被当前容量 j 计算过程中新更新的其他物品方案覆盖，形成了一条“可以从物品 A 跳到物品 B 再跳回 A”的路径，结果把所有排列都计入。

所以一个简单的自查方法：如果题目说“不考虑顺序”，那物品循环必须在外层；如果题目明确说“不同顺序算不同方案”，那容量循环在外层。这题属于前者。

4.2 初始化、边界和输入终止条件

边界情况是这类计数题最容易白给的地方。举几个具体场景：

第一，n=0 时输出什么？答案是 1，因为“什么都不选”本身是一个合法方案。很多同学初始化 dp[0]=1 之后，对这一行没有概念，遇到 n=0 直接不知道输出什么。记住计数型 DP 的通用约定：空组合算一种。

第二，m=0 且 n>0 时输出什么？答案是 0。没有纽扣，凑不出任何正数。代码里如果 m=0，for 循环一次都不跑，dp[n] 仍为初始值 "0"，输出自然正确。但如果你把 dp[0] 初始化为 0，那连 n=0 的情况也会错，所以初始化一定要用 dp[0]=1。

第三，关于输入终止条件。有些题目用 n=0 表示结束，有些用 EOF。我前面代码里写的是“读到 n 且 n 不为 0”，这是很多 UVa 题的风格。如果题面没有说明 n=0 终止，那就要改成普通的 while(cin >> n) 这种 EOF 读取方式。遇到多组输入题目，先认真看清楚结尾条件，不要想当然。

4.3 重复尺寸到底要不要去重

题目说纽扣“种类”不同，但没有明确说同一尺寸会不会重复给出。假设输入里出现了两个相同的尺寸，比如 2 和 2，那么按“每个输入代表一类纽扣”来算，选第一颗“尺寸2”和选第二颗“尺寸2”会被视为两种不同方案。但如果题目的本意是“尺寸为 2 的纽扣只有一种”，那就应该先去重再 DP。

我在实际处理时，会先读一遍题面，看它说的是“m 种不同尺寸”还是“m 个纽扣尺寸”。如果是后者，相同数字就应该合并。UVa 12316 的常规解法我没有提前去重，直接按输入的每一行作为一个种类处理，也能通过，因为在题目测试数据里，同一组内出现完全相同的尺寸的概率很低，而即使出现，题目也倾向于把它们当作不同种类，否则直接去重反而可能出错。

这算是一个比较刁钻的边界，如果你复现时遇到 WA，可以试着在输入处加一个sort+unique再跑一遍测试数据，看看答案是否变化。多数情况下不会变，但知道这个判断逻辑能帮你在排查时多一条路。

4.4 大数运算的性能陷阱

虽然这题 n 很小，但大数加法也有性能问题需要留意。字符串加法每次分配新字符串，如果内层循环次数多，分配次数就多。我见过有人把 dp 数组定义成vector<vector<int>>，每一位存大数的一位十进制数，然后手工用循环做加法，最后输出时拼接字符串。这种写法内存更大，代码更啰嗦，但性能其实差不多，因为 n 实在太小。

真正要小心的是：不要在每次加法时都调用类似to_string(stoi(a) + stoi(b))的函数。stoi会高位溢出，结果完全错误。也不要使用long long中间变量去接大数结果再转字符串，因为答案超过 long long 时直接就是错的。老老实实按位加，进位处理好，输出时不要在前面留多余的零。

5. 题型扩展与个人刷题体会

5.1 硬币问题的三个亲戚：最少数量、组合数、排列数

“用若干种硬币/纽扣/物品凑一个总额”这个模型几乎是动态规划里的常青树，出题人能变出无数花样。我这里列三种最经典的变体，刷题时可以对照着记。

第一种是最少硬币数量。状态 dp[j] 表示凑出 j 的最小硬币数，转移是 min。这类题对初始化要求是 dp[0]=0，其余为无穷大，循环方向依然是内层正序（完全背包）。

第二种是组合数，也就是本题的模式。要求每个组合不区分顺序，核心是物品循环在外层、容量循环在内层正序。

第三种是排列数，即顺序不同算不同方案。比如 LeetCode 377 这类题目，解法是把容量循环放在外层，物品循环放在内层。很多人在做这道题时突然想不明白，其实就是把本题的循环对调了一下，结果语义完全不同。

还有一个更细的坑：在组合数问题里，如果把“每种硬币无限”改成“每种硬币最多用 k 次”，那 dp 转移要从 0/1 背包变成多重背包计数，复杂度也要提高。建议先把这四种基础情况整理成一个表，刷题时对号入座。

5.2 带数量上限、带模数的变体

如果题目要求答案对某个大质数取模，比如模 1e9+7，那么大数计算就不用了，每一步加法后取模即可。这种题的坑在于：取模会改变“进位”逻辑，所以不能再用字符串加法，直接用long long做加法再取模。注意累加时两个 dp 值都要在模空间内，否则可能溢出。

如果需要限制每种纽扣最多使用次数，就把完全背包变成多重背包。常见做法是把第 i 种物品按二进制拆分，分成若干个 1 件、2 件、4 件……的 0/1 背包物品，再进行 DP。对于计数问题，更简单的方式是三重循环枚举第 i 种取多少件，但复杂度会上升到 (O(mn^2))。n 小的时候没问题，n 大的话必须优化。

还有一种变体是输出具体方案或者字典序最小的方案，这需要额外开一个 pre 数组记录转移来源。做这类题时，先把握住基础模型的转移方向，再一步步加条件，就不会跑偏。

5.3 一点个人刷题体会

我自己做这种“陪伴感很强”的题目时，最怕的是题目简单但读题不细。像 UVa 12316 这样的大数背包题，其实算法层面没有任何高级技巧，但把所有细节都做好，需要一点点经验积累。我总结了一条固定套路：拿到计数型背包题，先确定三件事——初始化、循环顺序、结果精度。把这三件事写在草稿纸上，再写代码，基本上不会出大问题。

之前在刷题群里见过一位同学，状态转移写得完全正确，但输出答案前加了一句“方案数可能很大，请对 1000000007 取模”，结果题目根本没让取模，直接 WA 了两页。这提醒我：做题前一定看清楚输出要求，是输出完整大数，还是输出模值。这题题目要求输出完整方案数，所以我们的 addString 方案是最稳妥的。

把这道题吃透之后，再遇到“硬币找零计数”“任意背包方案数”“整数拆分”问题，几乎可以秒杀。如果你正处在动态规划的入门阶段，建议动手把这题的二维写法先写一遍，再手动改成滚动数组。过程虽然有点重复，但对理解完全背包的本质帮助很大。我自己当年也是这样一步步过来的，现在看到这个题名，反而会想起陪奶奶一起数纽扣的温馨画面。