解题思路：

这题解题思路完全来自灵神 (灵茶山艾府)

https://leetcode.cn/problems/domino-and-tromino-tiling/solution/by-endlesscheng-umpp/

代码：

Python：

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

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numTilings(int n) {
        long long MOD = pow(10, 9) + 7;
        if (n == 1) return 1;
        long f[n + 1];
        f[0] = 1;
        f[1] = 1;
        f[2] = 2;
        for (int i = 3; i < n + 1; ++i) {
            f[i] = (f[i - 1] * 2 + f[i - 3]) % MOD;
        }
        return f[n];
    }
};