题目描述

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

XX  <- 多米诺

XX  <- "L" 托米诺
X

给定 N 的值，有多少种方法可以平铺 2 x N 的面板？返回值模 10^9 + 7。

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

样例

输入: 3
输出: 5
解释: 
下面列出了五种不同的方法，不同字母代表不同瓷砖：
XYZ XXZ XYY XXY XYY
XYZ YYZ XZZ XYY XXY

限制

• N 的范围是 [1, 1000]。

算法

(动态规划) $O(n)$

1. 状态 $f(i, 0)$ 表示 $i$ 之前的列都已经铺满了，第 $i$ 列没有铺任何瓷砖的方案数；$f(i, 1)$ 表示 $i$ 之前的列都已经铺满了，第 $i$ 列只铺了第一层的瓷砖的方案数；同理，$f(i, 2) 表示只铺了第二层的瓷砖的方案数，$f(i, 3)$表示第$i$ 列的两层都铺了瓷砖的方案数。
2. 初始时，$f(0, 0) = 1, f(0, 3) = 1$，其余都为 0。这是因为这两种状态各有一种铺法。
3. 转移时，对于 $f(i, 0)$，只能从 $f(i - 1, 3)$ 累加，因为要保证 $i$ 之前的列是满的才可以转移。通过枚举，不难发现，$f(i, 1) = f(i - 1, 0) + f(i - 1, 2)$，$f(i, 2) = f(i - 1, 0) + f(i - 1, 1)$，分别对应了两个不同情况的第 $i - 1$ 行，我们第 $i$ 行都有一种方式铺，所以可以转移。最后 $f(i, 3) = f(i - 1, 0) + f(i - 1, 1) + f(i - 1, 2) + f(i - 1, 3)$，也就是说对于 $i - 1$ 行的任何一种铺法，我们都有一种方法让 $i - 1$ 行铺满的同时，让第 $i$ 行的两层也都铺上瓷砖。
4. 最终答案显然为 $f(N - 1, 3)$。

时间复杂度

• 状态数为 $O(n)$ 个，转移仅需要常数时间，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的空间记录状态。

C++ 代码

class Solution {
public:
    int numTilings(int N) {
        const int mod = 1000000007;
        vector<vector<int>> f(N, vector(4, 0));

        f[0][0] = 1;
        f[0][3] = 1;

        for (int i = 1; i < N; i++) {
            f[i][0] = f[i - 1][3];
            f[i][1] = (f[i - 1][0] + f[i - 1][2]) % mod;
            f[i][2] = (f[i - 1][0] + f[i - 1][1]) % mod;
            f[i][3] = ((( f[i - 1][0] 
                        + f[i - 1][1]) % mod 
                        + f[i - 1][2]) % mod 
                        + f[i - 1][3]) % mod;
        }

        return f[N - 1][3];
    }
};