企业官网建设流程全解析

提起“火柴数字”，很多人第一反应还是小时候那种“移动一根火柴让等式成立”的脑筋急转弯。但放到算法题里，这个经典素材摇身一变，成了递推入门最顺手的练习场：给你N根火柴，问能拼出多少个不同的正整数、最大能拼到多少，甚至反过来问一个数字串要消耗多少根火柴。这类题目数据范围一大，暴力枚举根本撑不住，真正能稳定把答案算出来的方式，就是递推。这篇文章我打算把“火柴数字（简单递推）”这个题目从头拆到尾，从状态设计、转移方程、边界条件到代码实现、进阶变体逐层展开，还会拉上经典的“骨牌问题”做对照。适合刚开始刷递推题的同学，也适合想把手上的板子整理得更扎实的选手。

先说一个核心观点：火柴数字问题的难点从来不在“数火柴”，而在于你愿不愿意把它抽象成一个“按剩余火柴数划分状态”的递推模型。一旦这个模型立住了，剩下的无非是转移怎么写、边界怎么处理、代码怎么不写崩。

1. 火柴数字问题到底在考什么：递推的第一性原理

1.1 先还原题目场景：0到9每个数字到底吃几根火柴

要讨论火柴数字，第一步必须把“数字到火柴成本”的映射定下来。标准七段数码管里，每个数字对应的火柴根数是一个固定常量，绝大多数题目沿用的是这套映射：

我建议你每次做题前先把这张表写进代码里，因为有些题目会微调口径。比如有的版本把“0”算成7根，有的版本不允许拼出以0开头的多位数，甚至有的版本允许“0”单独作为一个数。你先把映射函数抄对，后面所有推导才不会崩。

以最经典的“恰好用完N根火柴，能拼出多少个不同的正整数（不含前导0）”为例。N=4的时候，答案一眼能看穿：可以拼出数字“4”（4根），也可以拼出“1”+“1”（2+2根）得到“11”，总共2种。N=5的时候，可以拼“2”、“3”、“5”这三个单个数字，还能拼“1”+“7”得到“17”，以及“7”+“1”得到“71”，一共5种。别看例子小，它已经把问题的味道带出来了：拼一个多位数的本质，是“若干数字按顺序拼接”，每一位都要消耗对应的火柴数。自问一句：给你N=100呢？用手穷举直接投降，这就是递推登场的时机。

1.2 为什么暴力枚举撑不住，递推却在“偷懒”

假设N=100，拼出来的数最长可能是50位（全用“1”，每个2根）。每一位可以取0到9的任意数字，候选空间接近10的50次方，别说枚举，光是生成一遍都是天文数字。

可如果你换个角度想：一个合法的正整数，它最后一位一定是一个数字d，而前面的部分一定是用剩余火柴拼出来的另一个合法串。于是“用N根火柴拼正整数”这个问题，就能拆成“枚举最后一位数字d，再递归处理剩余根数”的结构。这里有一个关键认知：子问题之间大量重叠。比如计算“用4根火柴拼”的时候，会用到“用2根火柴拼”；计算“用6根火柴拼”的时候，又会用到“用4根火柴拼”。如果每次遇到都重新递归算一遍，复杂度是指数级；但如果把每个“剩余根数”的答案记下来，后一次直接查表，这就是记忆化搜索，也就是递推的前身。

递推本质上是“把大规模问题拆成更小规模的同类问题”，用小规模答案拼出大规模答案，并且保证每个子问题只算一次。火柴数字正好是理解这件事的完美载体，因为“剩余火柴数”就是那个天然的状态维度，清晰、单调、不会出现环。

1.3 两个维度看递推：计数型递推和最优化递推

递推题可以粗略分成两类：一类问“有多少种”，叫计数型递推；另一类问“最大/最小是多少”，叫最优化递推。火柴数字两种都能考。

计数型的主线是：dp[i]表示“用i根火柴拼出合法串的方案数”，转移时枚举最后一位数字。最优化型则要改成：dp[i]存“用i根火柴能拼出的最大整数”或“最小整数”，转移时比较字符串/数值大小。无论哪种，三件事逃不掉：状态定义、转移方程、边界条件。状态错了，后面全错；转移漏了，答案偏小；边界没写对，样例都过不了。后面几节我会把这三件事在火柴数字上都过一遍。

2. 状态设计是关键：从“还剩几根火柴”开始

2.1 转移方程怎么写：dp[i] = Σ dp[i - cost[k]]

先给出一版最常见的递推写法。设cost[d]为数字d消耗的火柴根数，dp[i]表示“恰好用i根火柴，能拼出的数字串个数（允许串以0开头）”，转移方程是：

dp[i] = Σ_{d=0..9} dp[i - cost[d]]，条件是 i ≥ cost[d]

边界条件设dp[0] = 1。这个1不是凭空来的，它表示“空串”：不拼任何数字。为什么必须设成1？因为当你枚举最后一位数字d时，如果i刚好等于cost[d]，那么扣除d消耗的根数后，剩余0根，前面的部分必须是空串，这样整个串就是单数字d。如果dp[0] = 0，所有单个数字的情况就全部漏掉了。dp[0] = 1这种边界，是递推题里非常经典的一手，骨牌问题里的f[0] = 1也是同一个道理。

用N=4验证一下：dp[0]=1，dp[1]=0，dp[2]=1（拼“1”），dp[3]=1（拼“7”），dp[4] = dp[2]（最后一位放1，前面用2根）+ dp[0]（最后一位放4，前面空）= 1 + 1 = 2。和手算吻合。

2.2 首位不能是0：递推里最容易被忽略的边界条件

直接套用上面那个dp，所有以0开头的多位数都被算进去了，比如N=6时它会算出一个“0”后面接“1”的串“01”。题目如果要求的是一般意义下的正整数，这种串必须剔除。

标准的做法是拆成两个状态：g[i]表示“用i根火柴拼出任意数字串的个数，允许以0开头，也允许空串”；f[i]表示“用i根火柴拼出首位非0的正整数个数”。转移如下：

g[i] = Σ_{d=0..9} g[i - cost[d]] f[i] = Σ_{d=1..9} g[i - cost[d]] 边界依旧是 g[0] = 1。

这里f[i]的转移要特别解释一下：首位从1到9中选一个非0数字d，消耗cost[d]，剩下i - cost[d]根火柴去拼一个“任意串”，也就是g[i-cost[d]]。之所以后面用g而不是f，是因为首位之后允许出现0，比如“101”这种数字完全合法。把f和g分开，是这类题最容易拉开差距的细节。

拿N=6手算一把。g[0]=1，g[1]=0，g[2]=1，g[3]=1，g[4]=2，g[5]=5。g[6] = d=1时g[4]=2（对应“111”和“14”），d=2/3/5时g[1]=0，d=4时g[2]=1（对应“41”），d=6/9时g[0]=2（对应“6”和“9”），d=7时g[3]=1（对应“77”），d=0时g[0]=1（对应“0”），所以g[6]=2+1+2+1+1=7。再看f[6]：首位1消耗2根，后面g[4]=2，得到“111”和“14”两种；首位4消耗4根，后面g[2]=1，得到“41”一种；首位6消耗6根，后面g[0]=1，得到“6”；首位9同样得到“9”；首位7消耗3根，后面g[3]=1，得到“77”。合计f[6]=2+1+1+1+1=6。所以6根火柴能拼出111、14、41、6、9、77这6个正整数，数字“0”单独出现不算正整数，成功被排除。小心这个坑，很多初版代码挂就挂在这里。

2.3 取模、高精度和“必须用完”的题目口径

计数型递推的答案往往大得离谱。N=20时方案数已经在万级，N=100时轻松超过任何64位整数能承载的范围。所以题目通常会要求对某个大质数取模，常见的是1e9+7。做题时每一步加法和转移都记得取模，不要等最后才取，否则中间用long long也可能溢出。

另一个常见口径是“不超过N根火柴”而不是“恰好用完N根”。这两种差异很大：恰好用完是dp[N]；不超过N则是把dp[0]到dp[N]全部累加一遍。如果题目说“最多N根”，你还在傻傻只输出dp[N]，答案必然偏小。我习惯在读完题后立刻圈出“恰好”“至少”“不超过”这三个词，再决定用哪种统计方式。

如果题目不要求取模而是直接输出完整数值，那就得用高精度。C++可以自己写大数加法，或者用__int128撑一段；Python自带大整数，写这类题非常省心。所以做火柴数字递推题，Python的体验会比C++友好不少，除非你刻意想练大数模板。

3. 实操：从手算推导到跑通完整代码

3.1 先手算一轮：用小样例建立信心

我每次写递推代码前，一定会先在小范围手算出几组答案作为调试锚点。火柴数字这题，N从1到6的手算结果可以整理成这样：

只要你的代码在这几个小N上输出完全一致，边界和转移基本就没问题。相反，如果N=4输出3，说明把“01”这种前导0的串也算进去了；如果N=5输出4，说明漏了“71”或者“17”，检查转移枚举是否完整。

再往下，N=7你也可以手推一遍：f[7]的答案我直接给出来，是12个，有兴趣可以自己枚举验证。把前几项记熟，后面调试代码时非常管用。

3.2 C++完整实现：双dp方案

下面给出完整可运行的C++代码，使用f/g双dp方案处理前导0问题，并对1e9+7取模：

#include <bits/stdc++.h> using namespace std; const long long MOD = 1e9 + 7; const int cost[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; int main() { int N; cin >> N; vector<long long> g(N + 1, 0), f(N + 1, 0); g[0] = 1; // 空串：不拼任何数字 for (int i = 1; i <= N; i++) { // g[i]：允许前导0，任意数字串 for (int d = 0; d <= 9; d++) { if (i >= cost[d]) { g[i] = (g[i] + g[i - cost[d]]) % MOD; } } // f[i]：首位非0的正整数 for (int d = 1; d <= 9; d++) { if (i >= cost[d]) { f[i] = (f[i] + g[i - cost[d]]) % MOD; } } } cout << f[N] % MOD << endl; return 0; }

这段代码的时间复杂度是O(N * 10)，空间复杂度O(N)。对于N在10的6次方以下都能轻松跑完。为什么这里g和f要放在同一个循环里算？因为计算f[i]需要用到g[i-cost[d]]，而g[i-cost[d]]的下标一定小于i，在前面的轮次已经算好了，所以一维数组从1扫到N完全够用，不需要二维数组。

3.3 Python版本和空间优化技巧

Python版本同样简洁，大整数场景还能直接去掉取模：

cost = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6] def solve(N, mod=None): g = [0] * (N + 1) f = [0] * (N + 1) g[0] = 1 for i in range(1, N + 1): for d in range(10): if i >= cost[d]: g[i] = (g[i] + g[i - cost[d]]) for d in range(1, 10): if i >= cost[d]: f[i] = (f[i] + g[i - cost[d]]) if mod: g[i] %= mod f[i] %= mod return f[N] print(solve(6)) # 6

很多博客会吹“滚动数组优化”，说能把空间从O(N)压到O(1)。但火柴数字这个递推式不一样，dp[i]依赖于所有dp[i-cost[d]]，也就是可能依赖任意一个更小的下标。如果只保留几项，后面根本不知道前前前前一项是什么，所以滚动数组在这里并不适用。O(N)的一维数组已经是最优，别再折腾了。这也是一个认知点：不是所有递推都适合滚动数组，只有当依赖关系被限制在最近几项时（比如斐波那契只依赖前两项），滚动数组才有意义。

4. 进阶变体：从“有多少个”到“最大、最小数字”

4.1 “最大数字”的贪心与递推：为什么直接拼一堆1会翻车

问完方案数，题目换个角度：给定N根火柴，拼出的最大整数是多少？很多人第一反应是“1”最省火柴，所以尽量多用1，N是偶数就全拼1，N=6时也就是111。这个思路对不对？N=6时是对的，但N=7时立刻翻车：全拼“1”要2根一个，N=7不够整除，六位拼不出，拼三位111用掉6根还剩1根没处去；可实际上7根能拼出“711”吗？7的成本是3根，两个1成本4根，合计7根，“711”作为三位数整体大于任何以1开头的三位数，甚至大于“111”。所以最大数字问题的本质是两层目标：第一，位数尽量多，因为多一位数一定更大；第二，位数相同时，高位的数字尽量大。

位数最多意味着消耗尽可能小，而2根一根的“1”确实是位数最大化的主力。但每多一位，都要从总根数里扣掉2根；高位要想更大，就得用更高成本的数字（比如7成本3根、8成本7根），这会侵蚀位数。于是问题变成一个权衡：用同样的N根火柴，是用掉两根在低位继续放1，还是用三根在高位放7？这个权衡用贪心可以直接做，只是要小心余数；用递推也能做，设dp[i]为“用i根火柴拼出的最大数字串”，转移时枚举最后一位数字，在得到的所有候选串里取字典序最大即可。

这里有个容易踩的坑：说“字典序最大”不够严谨，位数不同的数字比大小应该先比位数，位数相同再比字典序。C++对string直接用大于号比的是字典序，“9”大于“11”是因为9的ASCII码更大，但这不代表9根火柴拼出的9一定大于11根火柴拼出的11——因为两者用的火柴数根本不同，压根不会出现在同一个dp[i]里比较。可一旦dp[i]内部出现不同位数的候选串，直接比字典序就会错。比如“111”和“77”用同样的根数时，字典序比较会说“7”开头的77大于"1"开头的111，实际上也确实77更大，但这只是巧合。更安全的做法是把串的长度作为第一比较键，长度相同时才比较字典序。这点务必在实现时处理好。

4.2 最小数字的边界条件：0不能开头，也不能单独输出

最小数字变体同样经典，而且比最大数字更麻烦。核心矛盾是“0”只要6根，在所有数字里属于成本较高的，看起来没什么用；但它可以作为非首位数字，比如101、200这种，让数字显著变小。同时0不能作为首位，否则“01”不是合法整数。有些题目还规定不能输出“0”本身，即使N=6时单独一个0在数学上是整数，在火柴题口径下往往也不算数。

递推写法里，dp[i]存最小数字串，比较规则是“长度短优先，长度相同取字典序小”。转移枚举首位后，剩余位可以用0到9任意数字，因此最小数字的转移同样要用到“允许0开头”的子状态。换句话说，最小数字题几乎绕不开双dp，或者你直接在状态里加一个标志位表示“当前是否已经放过非0首位”。

还有一个细节：如果N=2，只能拼出“1”，最小也是“1”；N=6可以拼出“6”（6根）和“0”（6根）这两个单数字，以及“11”（4根，多了2根没处放？不对，恰好用完的话“11”只用了4根不合法）。在恰好用完的口径下，N=6能拼的最小正整数是“6”还是“9”？“6”和“9”都只要6根，数字6更小，所以答案是6。如果允许“不超过”，那就变成N=6时可以用4根拼“11”，答案会直接变成“11”。题目一字之差，答案天壤之别。

4.3 和骨牌问题放在一起看：递推的两个经典套路

既然热词里有“骨牌问题”，这里必须拉出来对照。经典的骨牌问题是：用1×2和2×1两种骨牌铺满2×n的棋盘，方案数是多少？递推方程非常优雅：

f[n] = f[n-1] + f[n-2]

边界f[1]=1，f[2]=2。它的拆分逻辑是：看最后一列，要么竖着放一张1×2骨牌，剩下的2×(n-1)独立解决；要么横着放两张2×1骨牌，剩下的2×(n-2)独立解决。这不就是枚举“最后一步”的两种选择吗？

和火柴数字对比一下：

两个问题看似风马牛不相及，实质都是“把最后一件事枚举清楚，把剩余部分交给更小的状态”。一旦你意识到这一点，递推题的识别速度会快很多：看到“恰好用完N个什么东西拼成一个东西”，立刻想到按剩余量做状态；看到“铺满N长度的结构”，立刻想到最后一步有哪几种摆法。这两个套路覆盖了递推题里很大一部分，练熟火柴数字和骨牌问题，基本就摸到了计数的门道。

5. 常见问题与排查技巧实录

5.1 递推题最容易踩的五个坑（速查表）

根据我自己的刷题经验，火柴数字这类递推题里，翻车原因高度集中在下面五个。整理成一张表，方便自查：

除了表格里的这五个，还有一种不太显眼的坑：数组下标越界。很多人在枚举数字d时忘记检查i - cost[d]是否大于等于0，直接把负数下标传进数组。C++里这会读到未定义内存，表现是答案忽大忽小、时对时错。所以每次写if (i >= cost[d])这行条件，都不要省。

5.2 调试递推代码的三个实用技巧

技巧一：去掉取模，用小N对答案。取模会掩盖真实数值，让手算对比变得困难。我通常先在代码里关掉mod，输出N=1到8的完整序列，和手算表核对。只要前几项全对，大N正确性基本有保障。

技巧二：打印转移来源。只输出dp[N]等于黑盒，出错了也看不出是哪个环节错。我会临时加一段调试代码，在计算f[i]时打印“i=7, 从数字3转移, 来源=g[2]=1”，这样能直观看到每个状态的每个转移是否被触发。特别适合检查是不是漏了某些数字的枚举。

技巧三：从递归改记忆化再改递推。如果你对递推方向不熟，可以先用最笨的递归加上记忆化数组写一版，跑通后再观察递归函数的依赖方向，手动转成循环。递推和递归在数学上是同一件事，转换过程中能帮你把状态依赖图理清楚。

5.3 现场复盘一个真实Bug

我印象很深的一次翻车是：在g[i]和f[i]的转移里，我把g[0]设成0而不是1。当时想着“0根火柴当然什么都拼不出来”，结果N=4的答案从2变成了0，N=5从5变成了0。排查过程非常经典：先怀疑cost表抄错，检查几遍没问题；接着怀疑取模，关掉还是错；最后把dp数组打出来，发现从N=2开始就全是0，这才意识到是边界没了。g[0]=1这个“空串”设定，看似简单，却是整套递推的基石。从那以后我写计数递推，第一件事就是确认所有边界条件把0下标的情况覆盖到位。

还有一次是骨牌问题里把f[2]错写成1，导致所有偶数n的答案都少了一半。这类问题的共同教训是：递推题的正确性依赖两个锚点——边界条件和前几项手算值。两者都对不上，那一定是转移方程本身有问题，别急着调代码。

写在最后

玩火柴数字玩到后面，我发现它特别适合当递推题的“思维体操”。一个题目里同时藏了计数、前导0处理、最优化比较、空间复杂度分析四层考点，而且每层都能单独拎出来出题。我个人的习惯是：遇到任何递推计数题，先花三分钟手动推N=1到N=6的答案序列，再写代码；只要这段小序列对不上，就说明状态定义或者转移枚举有根本性问题，改代码之前先改思路。这种“先手算、再编码、最后对照”的流程，帮我省下的调试时间远比花掉的几分钟多。如果你正在刷递推，不妨也试试把火柴数字和骨牌问题并排做一遍，做完这两道，很多递推题的套路在你眼里就不再是黑盒了。