火柴数字递推与骨牌覆盖：从简单计数到动态规划思维

1. 这道题到底在考什么

1.1 从“火柴数字”说起

如果你刷算法题，八成见过这么一道“入门简单题”：给你 n 根火柴棒，问一共能拼出多少个不同的非负整数。每个数字消耗的火柴根数是固定的，比如 0 消耗 6 根，1 消耗 2 根，8 消耗 7 根，而且所有火柴必须全部用完，拼出来的数字不允许有前导零。

我第一次遇到时心里想的是：这有什么难的，枚举不就行了？结果一动手就发现，n 稍微给大一点，枚举直接爆炸。你根本不知道要枚举到多大范围，因为“数字的位数”不是固定的——n=20 的时候，既能拼出十位数，也能拼出二十几位的一长串数字，暴力枚举的搜索空间根本不是人能接受的。

后来我才反应过来，这道题的名字里藏着答案：简单递推。它考的不是枚举，不是贪心，而是你能不能把一个看起来像“无穷多种可能”的计数问题，压缩成一条简洁的状态转移关系。等你真正把递推式写出来，会发现代码短到只有十几行，但背后那层“为什么能这样拆”的思路，才是这道题真正的价值。

1.2 为什么枚举会炸，贪心又不对

先看最直觉的做法：我搜索所有由数字组成的串，判断总消耗是不是刚好等于 n。比如 n=50，拼一个 40 位的数字串也是完全合法的，这种串的数量是指数级的，根本数不完。所以枚举这条路，从根上就走不通。

贪心能不能行？也有很多人第一反应是：优先用消耗最少的数字 1（2根）来拼，这样位数最多。但问题是题目问的是“有多少种不同的数”，不是“最长能拼多长”。你一旦定下“优先用1”，就把 2、3、5 这些同样消耗5根的数字全部漏掉了；而且同一个数字串内部，即使总消耗相同，把其中一位从 1 换成 2，得到的也是完全不同的数，都必须计入。贪心只能求“最值”，不能求“计数”。

这里就引出一个关键的思维转变：计数问题不要去想“具体是哪个数”，而要去想“怎么把一个大问题拆成几个小问题，并且保证不重不漏”。这恰恰是递推最擅长的场景。

1.3 递推的直觉：把“拼数字”看成“拼字符串”

“拼成一个整数”这个说法会把人带偏，因为整数有前导零、有位数之类的额外限制。但换个角度：拼数字本质上就是在“拼一串字符”，每一位从 0-9 里挑一个，每个字符有固定的消耗，最后统计消耗总和为 n 的字符串个数。

一旦你看成字符串，思路就打开了。假设我已经用 i 根火柴拼好了某个字符串，现在想再拼一位，是不是只要枚举新加的这一位是哪个数字，然后看 i + 该数字消耗 是否等于目标值？换句话说，一个长串的计数，完全可以由“短串的计数”叠加出来。这就是递推的种子。

为了把这个问题讲透，下面我会完整走一遍推导过程。先给出数字消耗表，因为后面所有计算都依赖它：

这张表建议直接背下来，或者写代码时存成一个数组。需要注意 8 是消耗最多的，7 根；1 最省，才 2 根。这个“最省”和“最贵”的差异，直接决定了后面某些边界情况的答案。

2. 核心递推式是怎么推出来的

2.1 先算允许前导零的情况：g 数组

我一开始犯的错是直接定义 dp[n] 为“用 n 根火柴能拼出的整数个数”，然后试图一位一位转移。结果发现转不动，因为“首位不能为 0”这个限制让转移变得很别扭——你不知道当前处理的这一位到底是不是第一位，也就不知道该不该排除 0。

正确的姿势是拆分：先把“首位不能为 0”这个限制扔掉，算一个更宽松的数组 g[i]，表示“用 i 根火柴能拼出的数字串个数，允许前导零，空串也算一种”。

为什么空串也算？因为空串表示“还没拼任何字符”的状态。它是一个非常自然的递推起点：我用 0 根火柴，什么都还没拼，这当然是一种方案。就像爬楼梯问题里，站在第 0 级台阶也算一种状态一样。这个初始条件如果漏了，整个递推就全乱了。

接下来考虑如何构造 g[i]。假设我最后一位拼的是数字 d，那么前 i - cost[d] 根火柴拼的是一个任意串（允许前导零），它的数量正好是 g[i - cost[d]]。把所有可能的 d 累加起来，就得到：

g[i] = g[i - cost[0]] + g[i - cost[1]] + ... + g[i - cost[9]]

其中 cost[d] 是对应数字消耗的火柴数。翻译成大白话就是：一个由 i 根火柴拼成的串，要么最后一位是 0（前面用掉了 i-6 根），要么最后一位是 1（前面用掉了 i-2 根）……把所有可能情况加到一起。

这里有个很多人会想不通的点：为什么是“最后一位”而不是“第一位”？其实都可以，但“最后一位”更符合递推的直觉。我从前往后拼字符串，拼到第 i 根火柴时，最后做出的决策就是“选最后一个数字”，把前面的部分看成一个规模更小的同类问题。这个“看最后一步”的技巧，在动态规划里出现频率极高。

2.2 不允许前导零：首位单独处理

有了 g 数组，处理前导零就非常简单了。一个合法的整数，它的首位只能是 1-9，不能是 0。所以首位确定之后，剩下的位才是一个“允许前导零”的串。

于是得到核心公式：

f[n] = sum(g[n - cost[d]])，其中 d 从 1 到 9，且 n >= cost[d]

翻译过来：整数首位选了数字 d，消耗 cost[d] 根火柴，剩下 n - cost[d] 根火柴拼任意串，数量就是 g[n - cost[d]]。把所有首位选择加起来。

这里还有一个容易漏掉的细节：单个数字 0 本身是合法整数吗？当然是。但它无法通过“首位 d=1..9”的方式被统计进来。所以要额外补上：如果 n == cost[0] == 6，f[6] 还要加 1。很多参考代码会漏掉这一点，导致 n=6 时答案少一个。你别笑，这个坑我见过不少人踩，特别是在做对拍测试的时候才发现。

用一句话总结两个数组的分工：g 管“后面随便拼”，f 管“开头必须合法”。这个拆法不仅适用于这道题，也适用于一切带“首位限制”的数字计数问题，比如“不含前导零且每位不能重复”之类的题目。先把宽松版本算了，再在最高位做排除，思路会清爽很多。

2.3 代码落地与验证

光有公式没有代码不踏实。Python 版本我习惯这样写：

cost = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6] def solve(n): g = [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 - cost[d]] ans = 0 for d in range(1, 10): # 首位不能是0 if n >= cost[d]: ans += g[n - cost[d]] if n == cost[0]: # 单独的数字0 ans += 1 return ans

先拿几个小数据验证一下。n=1 时，任何数字都拼不出来，答案是 0。n=2 时，只能拼一个数字 1，答案是 1。n=3 时，只有 7 消耗 3 根，答案是 1。这两个结果都很直觉，说明至少边界没问题。

再算 n=5。首位选 1 消耗 2，剩下 3 根火柴，g[3] 等于多少？只有数字 7，所以是 1，对应“17”。首位选 7 消耗 3，剩下 2 根，g[2] = 1，对应“71”。首位选择 2、3、5 这三者消耗都是 5，剩下 0 根，g[0]=1，对应单个数字 2、3、5 各一个。这里注意首位选 1 之后我已经统计了“17”，那么单个数字 1 是首位选 1、剩余 0 根，也就是“11”？不对，单个数字 1 的消耗是 2， n=5 时首位选 1 后剩余 3 根，不是 0，所以单个 1 不属于 n=5 的可拼数字。但首位选 2、3、5 时剩余 0，各贡献一个。加起来 1 + 1 + 3 = 5。这样手算结果与程序逻辑一致，可以放心。

这个递推的时间复杂度是 O(n * 10)，空间可以优化成 O(n)。如果你不想提前开一个大数组，甚至可以用滚动数组只保留 g[i-7] 到 g[i] 这些值，因为单个数字最大消耗是 7。不过 n 不大的时候没必要，开一维数组最简单直观，代码也不容易写错。

3. 几种常见变体和边界处理

3.1 恰好用完与最多用完的区别

上面我们处理的是“恰好用完 n 根火柴”。但很多题目会问“不超过 n 根”，或者“可以不用完”。这两种问法在推导上有本质区别：恰好用完，你直接看 g[i] 和 f[i] 的精确值；不超过 n 根，你要求的是所有 f[1] + f[2] + ... + f[n] 的和。

如果把“恰好用完”理解成“刚好花光预算”，把“不超过”理解成“预算内随便花”，后者的状态转移就需要处理“预算没用完”的情况。通常做法是加一个维度或者定义前缀和。我个人建议不要贪图省事直接改状态，而是在原有 f 数组上做前缀和，因为这样 f 的语义保持清晰，后面遇到其他变体时也不容易弄混。

还有一种坑人的变体：题目里说“拼一个数字”，但隐含条件是“这个数字的数值不能超过 1000”之类的上限。这时候纯递推就不够了，因为 g 数组会统计出所有位数的数字串，位数多的数字天然超过上限。我的做法是加一维表示当前已经用了多少根火柴、已经拼到第几位，然后在位数超过上限位数时直接剪掉。

3.2 加上“数值不能超过上限”的约束

如果题目变成：给定 n 根火柴，能拼出多少个不超过 M 的非负整数，递推就复杂不少。因为“不超过 M”不是一个只跟位数有关的限制，它跟每一位的具体数值都有关。

比如 M=123，那首位就不能随便选 9，选了 9 整个数一定超过 123。这时你需要按“数字位与 M 的字典序比较”来做：从高位往低位枚举，维护一个“当前前缀是否已经严格小于 M 的前缀”的标记。这个技巧在数字 DP 里叫 isLimit 状态，本质还是递推，只是状态从一维变成了二维：

dp[pos][sticks][tight]

其中 pos 表示当前在拼第几位，sticks 表示已经消耗了多少火柴，tight 表示是否已经松绑。每拼一位，枚举 0-9，检查消耗是否够用，再根据 tight 判断这一位能不能取 M 对应位置的那个数字。算出来的答案就是不超过 M 的数字个数。

这个变体已经不是“简单递推”了，但它正好说明了一个事实：很多复杂的动态规划，都是从简单递推一路加限制条件演过来的。你先把 g、f 那套基础吃透，遇到带上限的版本，只需要在转移里多维护一个布尔状态，思路仍然是同一套：枚举“这一步选了什么数字”。

3.3 超大 n 时的优化思路

如果 n 给到 10^7 甚至更大，O(n) 的递推会有点吃力。这时候有两条优化路线。

第一条是矩阵快速幂。观察 g[i] 的转移，它只依赖 g[i-2]、g[i-3]、g[i-4]、g[i-5]、g[i-6]、g[i-7]（对应数字 1-9 的最小和最大消耗）。因为依赖是线性的、且系数固定，你可以把它写成矩阵形式，然后用矩阵快速幂把复杂度降到 O(k^3 log n)，k 是状态维度，这里大约 7。省下的时间相当可观。

第二条是特征方程/生成函数。如果你熟悉生成函数，g[i] 的生成函数其实是一个有理函数，分母由各数字消耗决定。用一次多项式求逆也能在 O(n) 之外的其他复杂度下得到通项，但这需要比较深的数学底子，不建议新手一上来就碰。

说实话，竞赛里 n 一般不会给到需要矩阵快速幂那么大。但如果哪天你遇到 n=10^9 的火柴计数题，别慌，先想想能不能用矩阵快速幂。这个点也体现了递推题的共同特点：递推式一旦写出来，剩下的事情就是怎么算得更快。

4. 从火柴数字到骨牌问题

4.1 经典 2×n 骨牌递推的推导过程

提到递推式，很多人脑子里第一个冒出来的其实是骨牌覆盖问题。比如经典的题目：用 1×2 的多米诺骨牌铺满一个 2×n 的长方形，问有多少种铺法。

这道题和火柴数字看着八竿子打不着，但推起来的感觉完全一样。设 F[n] 为铺满 2×n 矩形的方案数。看矩形的最后一列，有两种情况：

第一种，最后一块骨牌是竖着放的，正好盖住最后一列的上下一格。那么前面 2×(n-1) 的区域就变成一个规模更小的同类问题，方案数是 F[n-1]。

第二种，最后两格被两块横着放的骨牌盖住，上面一块、下面一块，每一块都横跨第 n-1 和第 n 列。这种情况下，前面 2×(n-2) 的区域又是同类子问题，方案数是 F[n-2]。

因为这两种情况互不重叠、又覆盖了所有可能，所以 F[n] = F[n-1] + F[n-2]。边界是 F[1]=1，F[2]=2。你看，这不就是斐波那契数列吗？整个推导过程跟火柴数字的 g[i] 转移一样：看最后一步，枚举最后一步有哪几种选择，把各种选择的子问题方案数加起来。

4.2 3×n 等复杂变体：递推式是“读”出来的

如果把 2×n 改成 3×n，事情就变得有意思了。3 是奇数，所以 n 为奇数时一块 1×2 的骨牌都摆不满，方案数直接是 0。只看 n 为偶数的情况，F[2]=3，F[4]=11。

这个递推式不像 2×n 那样一眼能看出来，但依然可以用“看最后一步”读出来。你盯住左上角那个格子，它只有两种放法：竖着放一块，或者横着放一块。如果竖着放，那么左下角也必须竖着放一块（否则空一格填不上），这会把问题拆成一个 3×(n-2) 的子问题加一个形状特殊的“拐角区域”。那个拐角区域的覆盖方式又不是简单的子问题，而是会引出一条独立的递推关系。你再继续往下拆，最终能整理出 F[n] = 4F[n-2] - F[n-4] 这个结果。

很多新手看到这种递推式会觉得像是天上掉下来的，其实它不是靠灵光一现，而是靠“枚举最后一格的放法 + 画图 + 不重不漏分类”。当你发现拆出来的子问题不是标准矩形时，别慌，把那个奇怪形状也当成一个新状态，继续递推就好。这就是“递推式是靠读题面读出来的”的真实含义：你每读出一个转移，就离完整的状态定义近一步。

4.3 两种问题的本质同构

如果把火柴数字和骨牌问题放在一起看，它们的共同骨架非常明显：

• 有一个明确的“消耗”概念。火柴题里消耗的是火柴根数，骨牌题里消耗的是矩形长度。
• 有一个“最后一步”的决策空间。火柴题里最后一步是选一个数字，骨牌题里最后一步是放一块竖骨牌还是两块横骨牌。
• 子问题与原问题同构。火柴题里“用 i-cost[d] 根火柴拼串”还是火柴题，骨牌题里“铺满 2×(n-1)”还是骨牌题。
• 初值很关键。火柴题里 g[0]=1 表示空串，骨牌题里 F[0]=1 表示空矩形。

我后来做题时养成了一个习惯：看到计数类问题，先别急着搜索或乱猜公式，先把“最后一步有哪几种选择”列出来，看看能不能写成“当前状态 = 若干个更小状态之和”。如果是，这道题基本就解决了一半。这个抽象能力不是天生的，是拿火柴数字、骨牌这类经典题反复练出来的。

5. 实操中的常见问题与避坑清单

5.1 初值、边界与取模的坑

根据我刷题和帮人看代码的经验，这道题的报错几乎都集中在几个固定位置。用一个表格列出来，方便你对照排查：

其中前三个坑是新手最容易踩的。尤其是 g[0]=1 这个点，很多人不理解空串为什么要算一种，直接设成 0，结果后面所有 g 全是 0。你只要记住：空串是“还没拼任何东西”的起点，它的存在不是为了表示“有一个空答案”，而是为了让“最后一位选数字”的转移能流畅地结束在 i-cost[d]==0 这个位置。

5.2 排查顺序与测试用例

如果对拍发现答案不对，我建议按固定顺序检查。先看边界小数据，n=1、n=2、n=3 能不能对上；再看 g 数组前几项，比如 g[2] 应该等于 1（只有 1），g[3] 应该等于 1（只有 7），g[4] 应该等于 2（4 和 11，注意这里指允许前导零情况）；最后再看 n=6 这种“单独 0 会被漏掉”的特殊点。

一旦中间某一项不对，问题几乎一定出在某个数字的消耗值写错上。这个消耗表很绕，5 和 6 特别容易记混：2、3、5 都是 5 根，6、9 才是 6 根，0 也是 6 根。我建议把消耗表单独抽成一个常量数组，并且在代码旁边注释清楚来源，别靠记忆硬写。

5.3 我的几条实操心得

第一，做这种计数题，一定要分清“组合数”和“排列数”。火柴数字拼出来的是不同字符串，每位位置不同，所以是排列，每一位都要纳入计数；而骨牌铺格子是按区域拆分，不存在“同一块骨牌换个位置算两次”的问题。搞混这两者，递推式会完全错乱。

第二，不要在还没写出转移方程前就急着写代码。我有一次手快，先写了循环才发现 g 的定义和 f 的定义重叠了，结果改了半天。后来学乖了：先在纸上把“状态定义 + 转移方程 + 初值”三样写全，再下手写代码，整个过程通常不超过五分钟。

第三，养成拿小样例手算的习惯。小样例的价值不只是验证答案，更重要的是逼你把转移的每一分支想清楚。比如 n=5 那个手算，你做一遍就会很直观地感受到“首位选择”和“剩余部分”是怎么拼到一起的，这种体感是看多少题解都换不来的。

最后还想多说一句和本题关系不大、但很实用的经验：当你把某一类题做透之后，再遇到新的计数题，会很自然地先问自己“最后一步是什么”。这听起来像废话，但我是真的在踩了无数次坑之后才意识到，大部分递推式不是“想”出来的，而是靠一遍遍画状态图、列分支“摸”出来的。火柴数字这道题最值得你记住的，不是那条 f[n] 公式本身，而是你亲手把它推出来的那个过程。