LeetCode 790. 多米诺和托米诺平铺
题目描述
题意分析
用覆盖两个格子的多米诺，以及覆盖三个格子的 L 形托米诺，完整铺满一个两行、
n列的棋盘。骨牌允许旋转，不能重叠、越界或留下空格，返回不同铺法数量对1000000007取模的结果。统计的是最终覆盖形态，同一种覆盖不会因为放置先后顺序不同而重复计数。L 形骨牌会让铺设边界上下不齐，因此不能只照搬仅有多米诺时的递推式。
解法：消去残缺状态后的三项递推
核心思路
[!blue]
定义
F[i]为完整两行i列棋盘的铺法数，再定义G[i]为同样棋盘缺少最右上角一格时的铺法数。缺少最右下角的情况由上下对称得到相同数量，所以只需保存一种指定缺角状态，但组合完整棋盘时要考虑两个方向。对
i >= 2，先看完整棋盘的最右一列。用一块竖多米诺覆盖它，前面剩F[i - 1]；用两块横多米诺一起覆盖最后两列，前面剩F[i - 2]；用一块 L 形骨牌同时覆盖最后一列两格及前一列的一格，剩下的就是一个缺角棋盘。上下两种方向各贡献G[i - 1]，因此F[i] = F[i - 1] + F[i - 2] + 2G[i - 1]。再看缺右上角的棋盘，最右侧只剩一个下格。它若由横多米诺覆盖，移去这块后会留下方向相反的缺角棋盘，贡献
G[i - 1]；若由 L 形骨牌连同前一列两格覆盖，前面剩完整棋盘，贡献F[i - 2]。所以G[i] = G[i - 1] + F[i - 2]，这里的递推用于i >= 2。这两组状态可以继续消元。比较
F[i]与F[i - 1]的完整棋盘公式，再用G[i - 1] - G[i - 2] = F[i - 3]代换，得到F[i] - F[i - 1] = F[i - 1] + F[i - 3]，也就是F[i] = 2F[i - 1] + F[i - 3]。这条简化公式从i = 3开始使用，来自完整与缺角状态的配合，不能只凭最后一块骨牌直接猜出。初值是
F[0] = 1，表示空棋盘有一种什么都不放的方案；F[1] = 1，只能竖放；F[2] = 2，可以两块竖放或两块横放。每轮只需要前三个旧状态，所以用a、b、c分别保存F[i - 3]、F[i - 2]、F[i - 1]，先算新值，再整体推进。逐轮取模保持结果余数正确，但
2 * c + a在取模之前可能超过 32 位范围，因此两种实现都使用 64 位中间变量。
解题步骤
- 小于两列时直接返回一；否则初始化三个完整棋盘状态为一、一、二。
- 从第三列开始，用
next = (2 * c + a) % MOD计算当前方案数。- 将旧状态按
a = b、b = c、c = next推进。- 最后返回保存
F[n]的c。
代码实现
class Solution {
public int numTilings(int n) {
if (n < 2) {
return 1;
}
long a = 1;
long b = 1;
long c = 2;
for (int i = 3; i <= n; i++) {
long next = (2 * c + a) % 1_000_000_007;
a = b;
b = c;
c = next;
}
return (int) c;
}
}
func numTilings(n int) int {
if n < 2 {
return 1
}
a, b, c := int64(1), int64(1), int64(2)
for i := 3; i <= n; i++ {
next := (2*c + a) % 1_000_000_007
a, b, c = b, c, next
}
return int(c)
}
复杂度分析
- 时间复杂度：$O(n)$，每个列数只计算一次常数时间的递推。
- 空间复杂度：$O(1)$，缺角状态已经消去，只保存三个完整状态和一个临时新值。
关键点总结
[!green]
- L 形骨牌引入缺角边界，先补全状态才能覆盖全部合法铺法。
- 完整棋盘中的系数二来自上下对称的两种缺角方向。
- 简化三项递推需要配套初值，先计算新项再覆盖旧项。
易错点总结
[!yellow]
- 只使用前一项与前两项相加，会漏掉由 L 形骨牌连接缺角边界的铺法。
- 将缺角状态当成同时包含两种方向，再在完整状态中额外乘二，会重复计数。
- 把空棋盘方案数设为零，会让从空前缀接出完整铺法的贡献消失。
- 在求
next之前覆盖a或c，会把递推需要的旧状态弄混。- 使用 32 位中间值，等溢出后再取模无法恢复正确结果。
- 把摆放顺序当成新方案，而非比较最终骨牌覆盖，会重复统计同一种平铺。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 70. 爬楼梯 | 简单 | 同样对方案数做滚动递推，本题必须先补全残缺边界状态，再消元得到三项公式。 |