Domino And Tromino Tiling

790. 多米诺和托米诺平铺

分析

状态表示：
- 用 f[i][j] 表示覆盖 2 * i 面板且第i列状态为 j 的方法数。这里的状态 j 表示第 i 列的覆盖情况，具体含义如下：
  - j = 0 ：第 i 列已完全覆盖
  - j = 1 ：第 i 列的上方未覆盖，下方已覆盖
  - j = 2 ：第 i 列的下方未覆盖，上方已覆盖
  - j = 3 ：第 i 列完全未覆盖
状态转移：
- 从第 i-1 列的状态 j 转移到第 i 列的状态 k 。需要考虑瓷砖的放置规则，以及状态变化的可行性
- 定义 w[j][k] 为从状态 j 转移到状态 k 的合法性：
  - w[j][k] = 1 ：表示可以从 j 转移到 k
  - w[j][k] = 0 ：表示不可以从 j 转移到 k
初始状态：
- f[0][0] = 1 ：初始时第 0 列完全覆盖
- 其他状态初始化为 0。
目标：
- 返回 f[n][0]，即第 n 列完全覆盖的方案数

时间复杂度

外层遍历列数 n ，内层枚举状态 j 和 k 各为常数 4 ，因此时间复杂度为 O(16n) = O(n)

空间复杂度

O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution
{
public:
    int numTilings(int n)
    {
        const int MOD = 1e9 + 7;

        // 转移矩阵，定义状态转移规则
        int w[4][4] = {
            {1, 1, 1, 1},
            {0, 0, 1, 1},
            {0, 1, 0, 1},
            {1, 0, 0, 0}
        };

        // 动态规划数组，f[i][j] 表示覆盖到第 i 列状态为 j 的方法数
        vector<vector<int>> f(n + 1, vector<int>(4));

        // 初始状态：第 0 列完全覆盖
        f[0][0] = 1;

        // 动态规划求解
        for (int i = 0; i < n; i++)
            for (int j = 0; j < 4; j++)
                for (int k = 0; k < 4; k++)
                    // 如果状态 j 可以转移到状态 k，则更新 f[i+1][k]
                    f[i + 1][k] = (f[i + 1][k] + f[i][j] * w[j][k]) % MOD;

        // 返回最终结果：覆盖到第 n 列且状态为 0 的方法数
        return f[n][0];
    }
};