面板平铺问题

LeetCode 790 Domino and Tromino Tiling

动态规划求解

首先定义状态，由于地板只有两行，因此我们不需要过多关注行的摆放，只需要关注列的摆放。
我们定义f(i)的含义是，1~i列已经铺完，并且i + 1的状态是(0, 0)。这里的状态表示是否有横向延伸的地砖。同理，我们定义g(i)，h(i)的含义分别是，1~i列已经铺完，i+1列的状态是(0, 1)和(1, 0)。
初始状态f(0) = 1，g(0) = 0，h(0) = 0。
我们穷举第i列的放置方式：1. 竖着摆放；2. domino两个往回延伸，并对齐；3. domino两个往回延伸，并没有对齐对齐；4. tromino往回延伸；5. tromino往后延伸。得到转移方程如下：

1. f(i) += f(i - 1)
2. f(i) += f(i - 2)
3. h(i) += g(i - 1), g(i) += h(i - 1)
4. f(i) += g(i - 2), f(i) += h(i - 2)

5. g(i) += f(i - 1), h(i) = f(i - 1)

   代码

   class Solution {
   public:
    int numTilings(int N) {
        const int mod = 1e9 + 7;
        // next state is (0, 0), [0 ~ i] has tiled
        vector<long long> f(N + 1, 0);
        // next state is (0, 1), [0 ~ i] has tiled
        vector<long long> g(N + 1, 0);
        // next state is (1, 0), [0 ~ i] has tiled
        vector<long long> h(N + 1, 0);
        f[0] = 1;
        for (int i = 1; i <= N; i ++) {
            f[i] = f[i - 1];
            g[i] = f[i - 1];
            h[i] = f[i - 1];
            if (i > 1) {
                f[i] += f[i - 2] % mod;
                f[i] += g[i - 2] % mod;
                f[i] += h[i - 2] % mod;
            }
            g[i] += h[i - 1] % mod;
            h[i] += g[i - 1] % mod;
        }
        return f[N] % mod;
    }
   };