LeetCode 790. 多米诺和托米诺平铺
目录
题目描述
题意分析
题目目标：用 $2 \times 1$ 的多米诺骨牌和 L 形的三格托米诺骨牌铺满 $2 \times n$ 的棋盘，两种骨牌都可以任意旋转，求本质不同的铺法总数，对 $10^9 + 7$ 取模。
核心约束：两点。第一，$n$ 最大到 1000，而答案是指数增长的，必须边算边取模，不能最后再取。第二，托米诺占 3 格且横跨两列，这意味着铺放过程中会产生「一列已经填了一半」的残缺边界——这正是本题比爬楼梯难的地方：单纯按「铺满前 $i$ 列」定义状态是不封闭的，转移时会碰到没定义过的中间形态。
边界处理：$n = 1$ 时只能竖放一块多米诺，答案 1；$n = 2$ 时是两竖或两横，答案 2；$n = 3$ 时答案 5，这是第一个能体现托米诺贡献的规模，也是验证递推是否正确的最小用例。
实现取舍：可以引入辅助量把状态补全成三阶线性递推 $dp_i = 2dp_{i-1} + dp_{i-3}$，也可以直接维护「扫描前沿的四种边界形态」做常数空间的状态机。两者等价，前者便于讲清推导，后者便于写成滚动实现——本文先推前者，代码用后者。
解法：动态规划递推
核心思路
暴力枚举每块骨牌的位置显然不可行，方案数在 $n = 1000$ 时是天文数字。第一反应是仿照爬楼梯设 $dp_i$ = 铺满 $2 \times i$ 的方案数，然后按「最后铺的是什么」分类。
分类到一半就会卡住。最后如果是一块竖骨牌，前面剩 $2 \times (i-1)$，贡献 $dp_{i-1}$；如果是上下两块横骨牌，前面剩 $2 \times (i-2)$，贡献 $dp_{i-2}$；但如果最后用到了托米诺，它会把某一列咬掉一半，剩下的不是一个完整的矩形，$dp$ 描述不了。这就是瓶颈：状态定义不封闭。
补全的办法是引入第二个量。设 $p_i$ 表示「铺满 $2 \times i$ 的矩形，外加第 $i+1$ 列的某一行多出一格」的方案数——因为棋盘上下对称，多出上面那格和多出下面那格的方案数相同，用一个 $p_i$ 就够，用到时乘 2 即可。
于是两个递推同时成立。对 $dp_i$：最后一段要么是竖骨牌（$dp_{i-1}$），要么是两块横骨牌（$dp_{i-2}$），要么是一块托米诺把某个残缺边界补平（上下两种朝向，$2p_{i-2}$），即
\(dp_i = dp_{i-1} + dp_{i-2} + 2p_{i-2}\)
对 $p_i$：那个凸出的单格要么由一块托米诺产生（前面是完整矩形，$dp_{i-1}$），要么由一块横骨牌把已有的凸起再推远一列（$p_{i-1}$），即
\(p_i = dp_{i-1} + p_{i-1}\)
把 $p$ 消掉即得漂亮的三阶递推
\(dp_i = 2dp_{i-1} + dp_{i-3}\)
初值 $dp_0 = 1$（空棋盘算一种铺法）、$dp_1 = 1$、$dp_2 = 2$。代入验证：$dp_3 = 2 \times 2 + 1 = 5$，$dp_4 = 2 \times 5 + 1 = 11$，$dp_5 = 2 \times 11 + 2 = 24$，与题目给的样例一致。
代码采用的是与之等价的四状态自动机写法：把「扫描前沿的边界形态」显式建模成四种——
f[0]边界平齐（前面若干列已铺满，不向右凸出）、f[1]上方凸出一格、f[2]下方凸出一格、f[3]上下各凸出一格。每处理一列，四个量按固定的规则互相流转，其中g[0]汇总了全部四种前驱（这正是「无论此前是哪种残缺形态，都存在恰好一种方式把它补齐成平边界」的体现），g[3] = f[0]表示双凸边界只能由平齐边界放两块横骨牌产生，g[1] = f[2] + f[3]、g[2] = f[1] + f[3]则是单侧凸起的两种来源。由于骨牌集合左右镜像对称，这套自动机与常见的「从左往右」版本互为转置，最终读取的f[0]完全相同。
不变量一句话：每轮循环结束时，
f[j]表示已经处理完 $i$ 列、且扫描前沿呈第 $j$ 种形态的方案数。答案是循环 $n$ 轮后的f[0]——边界平齐意味着棋盘恰好被铺满，没有骨牌越过右边界。
解题步骤
第一步：初始化
f = {1, 0, 0, 0}。 为什么只有f[0]是 1：起点是「还没铺任何一列、边界平齐」，这种形态存在且唯一；其余三种凸起形态在还没放任何骨牌时不可能出现，计数为 0。
第二步：循环 $n$ 次，每次用旧的
f算出新的g，再整体替换。 为什么必须用独立的g而不是就地更新f：四个更新式都依赖同一轮的旧值，就地更新会让后算的式子读到已被覆盖的新值。这是滚动数组最经典的陷阱。
第三步：
g[0] = f[0] + f[1] + f[2] + f[3]。 为什么四种前驱都要算进来：无论前一列留下的是平齐还是任何一种凸起，都恰好存在一种放法把这一列补成平齐边界，所以四条路径各贡献一次。
第四步：
g[1] = f[2] + f[3]，g[2] = f[1] + f[3]。 为什么单侧凸起只有两个来源：一是对侧凸起的状态被一块横骨牌「换边」推进，二是双凸状态填掉其中一侧。两式关于上下对称，这也解释了为什么推导时可以只设一个 $p_i$。
第五步：
g[3] = f[0]。 为什么只能来自平齐：只有在边界完全平整时，才能同时铺上下两块横骨牌，一次性把两个凸起做出来。
第六步：每一步都对 $10^9 + 7$ 取模，最后返回
f[0]。 为什么用long（Go 里int已是 64 位）：四项相加最大接近 $4 \times 10^9$，超过 32 位有符号整数上限，先加后取模会溢出成负数。
以 $n = 4$ 走一遍（每一步列出
f的四个分量）：
初始：
f = [1, 0, 0, 0]。
第 1 列：
g[0] = 1+0+0+0 = 1；g[1] = f[2]+f[3] = 0；g[2] = f[1]+f[3] = 0；g[3] = f[0] = 1。得到f = [1, 0, 0, 1]。此时f[0] = 1正是 $dp_1 = 1$（一块竖骨牌），而f[3] = 1对应「铺了两块横骨牌、它们都伸进第 2 列」这一种形态。
第 2 列：
g[0] = 1+0+0+1 = 2；g[1] = f[2]+f[3] = 0+1 = 1；g[2] = f[1]+f[3] = 0+1 = 1；g[3] = f[0] = 1。得到f = [2, 1, 1, 1]。f[0] = 2即 $dp_2 = 2$（两竖 / 两横），验证通过。
第 3 列：
g[0] = 2+1+1+1 = 5；g[1] = 1+1 = 2；g[2] = 1+1 = 2；g[3] = 2。得到f = [5, 2, 2, 2]。f[0] = 5即 $dp_3 = 5$——这是第一次用上托米诺的规模，五种铺法分别是：三竖、竖+两横、两横+竖、以及两种由一块托米诺加一块多米诺构成的方案。同时注意f[1] = 2，它表示「铺满 $2 \times 3$ 后上方多出一格」的方案数，正好等于前面推导里的 $p_3 = dp_2 + p_2 = 2 + 1 = 2$，两套推导对上了。
第 4 列：
g[0] = 5+2+2+2 = 11。返回f[0] = 11，与 $dp_4 = 2 \times 5 + 1 = 11$ 一致，也与题目样例一致。
代码实现
class Solution {
public int numTilings(int n) {
long[] f = {1, 0, 0, 0};
int mod = (int) 1e9 + 7;
for (int i = 1; i <= n; ++i) {
long[] g = new long[4];
g[0] = (f[0] + f[1] + f[2] + f[3]) % mod;
g[1] = (f[2] + f[3]) % mod;
g[2] = (f[1] + f[3]) % mod;
g[3] = f[0];
f = g;
}
return (int) f[0];
}
}
func numTilings(n int) int {
f := [4]int{}
f[0] = 1
const mod int = 1e9 + 7
for i := 1; i <= n; i++ {
g := [4]int{}
g[0] = (f[0] + f[1] + f[2] + f[3]) % mod
g[1] = (f[2] + f[3]) % mod
g[2] = (f[1] + f[3]) % mod
g[3] = f[0]
f = g
}
return f[0]
}
复杂度分析
- 时间复杂度：$O(n)$。凭什么：主循环恰好执行 $n$ 轮，每轮只做常数次加法、取模与赋值，四个状态的数量与 $n$ 无关。
- 空间复杂度：$O(1)$。凭什么：任意时刻只保留上一列的四个状态值和本列的四个新值，不保存历史序列；即便按三阶递推实现也只需三个滚动变量。
关键点总结
- 状态定义不封闭时，补一个辅助状态而不是硬凑转移。 本题的 $p_i$（带一格凸起的残缺矩形）就是那把钥匙，认出「托米诺会咬出半列」是全题的分水岭。
- 把「扫描前沿的形状」当作状态，是所有轮廓线 DP 的共同套路。 从 $2 \times n$ 推广到 $m \times n$ 时，四种形态会变成 $2^m$ 种掩码，骨架完全一样。
- 滚动更新必须用临时数组，不能就地覆盖。 四个式子共享同一轮的旧值，这是本题最容易埋雷的实现细节。
- 取模要放在每次加法之后，且中间量用 64 位。 四项相加会突破 32 位上界，「最后统一取模」在这类计数题里必错。
- 初值 $dp_0 = 1$ 的含义是「空棋盘有一种铺法」。 计数类递推里空集算一种，取 0 会让整条递推全部塌成 0。
- 面试视角：不要一上来就默写四状态代码。正确顺序是：先按「最后一块骨牌是什么」分类 → 撞上残缺边界 → 引入 $p_i$ 补全 → 联立消元得到 $dp_i = 2dp_{i-1} + dp_{i-3}$ → 说明它等价于常数空间的四状态自动机。面试官若追问「怎么验证递推对不对」，答「代入 $n = 3$ 应得 5、$n = 4$ 应得 11」——手算最小规模是这类计数题唯一可靠的自检手段。
易错点总结
- 错误写法：就地更新，写成
f[0] = f[0]+f[1]+f[2]+f[3]; f[1] = f[2]+f[3]; ... f[3] = f[0];→ 用例 $n = 3$，f[3]读到的是已经被覆盖的新f[0]，得到 6 而不是 5；必须用临时数组g。- 错误写法：只写 $dp_i = dp_{i-1} + dp_{i-2}$（照搬爬楼梯） → 用例 $n = 3$，得到 3，漏掉了两种用托米诺的铺法，期望 5。
- 错误写法：递推写成 $dp_i = 2dp_{i-1} + dp_{i-2}$ → 用例 $n = 3$ 得到 $2 \times 2 + 1 = 5$ 碰巧正确，但 $n = 4$ 得到 $2 \times 5 + 2 = 12$，期望 11；错误的项要到第四项才暴露，这正是必须多验一组的原因。
- 错误写法：把 $p_i$ 的两种朝向漏乘 2，写成 $dp_i = dp_{i-1} + dp_{i-2} + p_{i-2}$ → 用例 $n = 3$ 得到 4，期望 5。
- 错误写法：初值取 $dp_0 = 0$ → 用例 $n = 3$，三阶递推 $dp_3 = 2dp_2 + dp_0$ 少了 1，得到 4；对应到四状态写法就是
f全零，任何 $n$ 都返回 0。- 错误写法：
g[3] = f[0]写成g[3] = f[0] + f[3]→ 用例 $n = 4$，f[3]被重复累计，得到 13 而非 11。- 错误写法：
g[1] = f[2]漏掉f[3]这一项 → 用例 $n = 3$，第 2 轮后f变成[2, 0, 1, 1]而不是[2, 1, 1, 1]，第 3 轮得到 4，期望 5。- 错误写法：中间量用
int存四项之和 → 用例 $n$ 较大时四个接近 $10^9$ 的数相加达到 $4 \times 10^9$，超过int上限溢出为负数，之后取模得到负答案。- 错误写法：循环结束后才统一取模 → 用例 $n = 30$ 左右答案就已经远超
long的表示范围，溢出后结果完全错误。- 错误写法：循环写成
for (int i = 1; i < n; ++i)→ 用例 $n = 4$，只迭代 3 轮，返回 5（即 $dp_3$），整体差一列。- 错误写法：认为 $n = 1$ 需要特判返回 0（「一列放不下托米诺」） → 用例 $n = 1$，竖放一块多米诺即可，期望 1。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 70. 爬楼梯 | 简单 | 二阶递推且状态天然封闭，不需要引入辅助状态来描述残缺边界 |
| 91. 解码方法 | 中等 | 转移是否合法取决于字符内容，重点在前导零与两位数范围的判定而非形态枚举 |
| 1137. 第 N 个泰波那契数 | 简单 | 同为三阶线性递推，可用来单独练滚动变量的更新顺序 |
| 面试题 08.01. 三步问题 | 简单 | 三阶递推加大数取模，考点集中在何时取模以避免溢出 |