多米诺和托米诺平铺 图解题解

一块 2×n 棋盘，多米诺加 L 形托米诺能铺出多少种花样

棋盘是 2 行 n 列。两种砖：2×1 的多米诺，横竖都行；L 形的托米诺，占三格、缺一角。用任意多块不重叠铺满，问有几种铺法，结果对 1e9+7 取模（取模=除以 1e9+7 只留余数，防数字大到存不下；1e9+7 是常用大质数）。n=1 只能竖一块多米诺得 1 种，n=3 有 5 种，n=4 有 11 种。

摆法随 n 指数翻，逐一枚举为什么数不完

把砖一块块摆、摆满就记一种，每往右推一列就分叉一次，铺法数随 n 指数级膨胀，n 一大数不过来；铺到一半的局面在算后面时又被从头重算。把「铺满前 i 列有几种」这个子问题算一次存下来复用，就是动态规划（把「铺满前 i 列」的答案存下来，后面直接取）。

只记「铺满前 i 列」，为什么推着推着会卡住

定义 dp[i] 为铺满 2×i 棋盘的方案数，答案是 dp[n]。可只盯它会卡壳：从左往右铺时两列分界线不总齐平。一块 L 形托米诺会让边界凸出一个角——前面铺满了，第 i 列却只填一格、另一格空着。这种「差一个角」的半满局面 dp[i] 装不下，得再补一个状态 gap[i]：前 i 列铺满、只在末列凸出一角的方案数。

补上「差一个角」的状态，递推怎么就成了 2·前一项加前第三项

给两个状态各列转移。铺满第 i 列有三条收尾方式：dp[i-1] 右边竖插一块多米诺、dp[i-2] 右边平放两块横多米诺、或拿托米诺补一个带角的 gap 局面（gap 有两种镜像方向，凑出系数 2）。

把两条式子联立、代入消去 gap（联立=把两条式子摆一起，消元=用代入法把 gap 约掉，只剩 dp），留下只含 dp 的递推 dp[i]=2·dp[i-1]+dp[i-3]。要紧的是：系数 2 和「前第三项」是消元后的代数结果，不对应具体铺法，别硬找图形对应。gap 这个辅助状态是这题的枢纽，少了它下面的消元根本联立不起来。

拿 n=3、n=4 亲手把 dp 推出 5 和 11

先摆好三个边界：dp[0]=1（空棋盘算一种）、dp[1]=1（宽 1 只能竖一块）、dp[2]=2（宽 2 有两竖和两横）。递推要读 dp[i-3]，起手须凑齐前三项。套 dp[i]=2·dp[i-1]+dp[i-3]：dp[3]=2×dp[2]+dp[0]=2×2+1=5，对上题面 n=3；dp[4]=2×dp[3]+dp[1]=2×5+1=11，对上 n=4。逐格推到 dp[8]，整条数组是 1、1、2、5、11、24、53、117、258。

漏掉系数 2，dp[4] 为什么会算成 6

从第 3 项推到第 n 项一趟线性循环，每步几次乘加取模，时间 O(n)；数组长 n+1，空间 O(n)，回看前一项和前第三项即可，压成三个滚动变量降到 O(1)。

漏系数 2 最常见，写成 dp[i]=dp[i-1]+dp[i-3]，dp[4] 会算成 6 而不是 11。取模也别忘——2×dp[i-1]+dp[i-3] 一次加法就能顶破 32 位翻成负数，C++/Java 得用 64 位、每步取模。边界还得铺满前三项：第 3 项要读 dp[0] 又得先有 dp[2]，只铺 dp[0]、dp[1] 就开推会读到没初始化的 0。

Python

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 10**9 + 7
        if n <= 2:
            return n
        dp = [0] * (n + 1)
        dp[0], dp[1], dp[2] = 1, 1, 2
        for i in range(3, n + 1):
            dp[i] = (2 * dp[i-1] + dp[i-3]) % MOD
        return dp[n]

C++

#include <vector>
using namespace std;
class Solution {
public:
    int numTilings(int n) {
        const int MOD = 1000000007;
        if (n <= 2) return n;
        vector<long long> dp(n + 1);
        dp[0] = dp[1] = 1; dp[2] = 2;
        for (int i = 3; i <= n; ++i) dp[i] = (2 * dp[i-1] + dp[i-3]) % MOD;
        return dp[n];
    }
};

Java

import java.util.*;
class Solution {
    public int numTilings(int n) {
        int MOD = 1_000_000_007;
        if (n <= 2) return n;
        long[] dp = new long[n + 1];
        dp[0] = dp[1] = 1; dp[2] = 2;
        for (int i = 3; i <= n; i++) dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD;
        return (int) dp[n];
    }
}