算法热题——多米诺和托米诺平铺

目录

题目链接：790. 多米诺和托米诺平铺 - 力扣（LeetCode）

题目描述

解法一：动态规划

题目回顾

🔍 解题核心思想

🧮 状态定义

状态转移

dp[i][0] 的转移来源：

dp[i][1] 的转移来源：

dp[i][2] 的转移来源：

边界条件

最终答案

总结：为什么这样设计状态？

示例分析：n=3

Java写法：

C++写法：

运行时间

时间复杂度和空间复杂度

时间复杂度

空间复杂度

总结

---

题目链接：790. 多米诺和托米诺平铺 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。

给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 + 7 取模 的值。

平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。

示例 1:

输入: n = 3
输出: 5
解释: 五种不同的方法如上所示。

示例 2:

输入: n = 1
输出: 1

提示：

• 1 <= n <= 1000

---

解法一：动态规划

题目回顾

我们要用两种瓷砖平铺一个 2 x n 的面板：

• 多米诺瓷砖（Domino）：2 x 1 或者 1 x 2
• 托米诺瓷砖（Tromino）："L" 形，3个格子组成

瓷砖可以旋转，所以 "L" 型有四种方向。目标是求出能铺满整个面板的不同方式数量。

---

🔍 解题核心思想

这道题是一个非常非常非常经典的组合计数 + 动态规划问题。

由于瓷砖形状不规则（尤其是 L 型），不能简单地像斐波那契那样只考虑前面几个完整铺满的状态。我们在这里呢，还需要考虑一些“部分铺满”的情况，从而帮助我们进行状态转移。

---

🧮 状态定义

我们使用以下三种状态来描述铺到第 i 列时的情况：

状态	含义说明
dp[i][0]	前 i 列已经完全铺满
dp[i][1]	前 i 列已铺完，且第 i+1 列上面一个格子空着（顶部缺失）
dp[i][2]	前 i 列已铺完，且第 i+1 列下面一个格子空着（底部缺失）

注意：状态 1 和 2 是一种中间状态，表示还没有完全铺满，但某些位置已经被覆盖了。

---

状态转移

我们可以看看出每种状态之间可能的转换：

dp[i][0] 的转移来源：

要铺满前 i 列，可以从以下几种情况转移而来：

1. 在 i-1 处铺了一个竖直的 Domino → dp[i-1][0]
2. 在 i-2 处铺了两个横放 Domino → dp[i-2][0]
3. 在 i-1 处有一个顶部缺失的状态（dp[i-1][1]），然后加上一个 L 型补上缺口
4. 在 i-1 处有一个底部缺失的状态（dp[i-1][2]），然后加一个 L 型补上缺口

所以：

dp[i][0] = dp[i-1][0] + dp[i-2][0] + dp[i-1][1] + dp[i-1][2]

---

dp[i][1] 的转移来源：

表示当前列铺完了，下一列少一个上面的格子：

这种情况可能是这样的：

1. 在 i-2 处完全铺满，然后在 i-1 和 i 的位置放一个 L 型 → dp[i-2][0]
2. 在 i-1 处是底部缺失状态（dp[i-1][2]），然后在当前位置加一个 Domino 补上缺口

所以：

dp[i][1] = dp[i-2][0] + dp[i-1][2]

---

dp[i][2] 的转移来源：

与 dp[i][1] 对称，所以只是缺的是下面那个格子：

1. 在 i-2 处完全铺满，然后加一个倒置的 L 型 → dp[i-2][0]
2. 在 i-1 处是顶部缺失状态（dp[i-1][1]），加一个 Domino 补缺口

所以：

dp[i][2] = dp[i-2][0] + dp[i-1][1]

---

边界条件

• dp[0][0] = 1：没有格子也是一种铺法（空集）
• dp[1][0] = 1：只能用一个竖直 Domino
• dp[1][1] = 0、dp[1][2] = 0：不可能出现缺一块的状态

---

最终答案

最后的答案就是：

dp[n][0]

即：铺满 2 x n 的所有方法数。

---

总结：为什么这样设计状态？

        因为瓷砖中包含了 L 型（非矩形），所以我们必须考虑“未完全铺满”的中间状态。否则就无法处理这些“带缺口”的铺法。

        如果只有 Domino 瓷砖，那么只需要 dp[i] = dp[i-1] + dp[i-2] 就可以解决问题（类似于斐波那契）。但加入 L 型后，就需要扩展状态来记录更多细节。

---

示例分析：n=3

输入：n=3
输出：5

我们可以通过上述递推得到如下结果：

i	dp[i][0]	dp[i][1]	dp[i][2]
0	1	0	0
1	1	0	0
2	2	1	1
3	5	2	2

最终 dp[3][0] = 5，正确！

Java写法：

class Solution {
    private static final int MOD = 1000000007;

    public int numTilings(int n) {
        if (n == 0)
            return 1;
        if (n == 1)
            return 1;

        long[][] dp = new long[n + 1][3];

        // Base cases
        dp[0][0] = 1; // empty tiling
        dp[1][0] = 1; // one vertical domino

        for (int i = 2; i <= n; i++) {
            // dp[i][0]: fully filled up to i
            dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD;

            // dp[i][1]: top of i+1 is missing
            dp[i][1] = (dp[i - 2][0] + dp[i - 1][2]) % MOD;

            // dp[i][2]: bottom of i+1 is missing
            dp[i][2] = (dp[i - 2][0] + dp[i - 1][1]) % MOD;
        }

        return (int) (dp[n][0] % MOD);
    }
}

C++写法：

class Solution {
public:
    const int MOD = 1000000007;

    int numTilings(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;

        // dp[i][0]: 完全铺满前 i 列
        // dp[i][1]: 铺完前 i 列，第 i+1 列上面格子空着
        // dp[i][2]: 铺完前 i 列，第 i+1 列下面格子空着
        long** dp = new long*[n + 1];
        for (int i = 0; i <= n; ++i) {
            dp[i] = new long[3]{0};
        }

        dp[0][0] = 1; // 空也是一种铺法
        dp[1][0] = 1; // 只能竖放一个 domino

        for (int i = 2; i <= n; ++i) {
            dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD;
            dp[i][1] = (dp[i - 2][0] + dp[i - 1][2]) % MOD;
            dp[i][2] = (dp[i - 2][0] + dp[i - 1][1]) % MOD;
        }

        int result = dp[n][0];
        
        // 释放内存
        for (int i = 0; i <= n; ++i) {
            delete[] dp[i];
        }
        delete[] dp;

        return result;
    }
};

运行时间

时间复杂度和空间复杂度

时间复杂度

• 时间复杂度: O(n)
  • 我们只需要遍历一次从 2 到 n 的循环。在每次迭代中，我们执行的是常数时间内完成的操作（主要是加法和取模运算）。因此，总的时间复杂度是线性的，即 O(n)。

空间复杂度

• 空间复杂度: O(n)
  • 在原始实现中，我们使用了一个二维数组 dp 来保存状态，大小为 (n+1) x 3。因此，直接的空间复杂度是 O(n)，因为我们需要存储每列的三种状态。

---

---

总结

       今天我们采用动态规划方法解决平铺 2 x n 面板的问题，通过维护三种状态来考虑不同类型的瓷砖铺设方式。初始实现的时间复杂度为 O(n)，空间复杂度为 O(n)，但可以通过滚动数组技术将空间复杂度优化至 O(1)。该方法有效地计算了所有可能的铺砌方式，并对结果取模 10^9 + 7 以确保数值稳定性。这样，在最优情况下，我们只需要线性时间以及常数级别的额外空间就能解决问题。