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

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

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

状态定义: f[i][k]表示前i - 1列已经排好且第i列的格子的状态为k的方案数

f[i][0]:前i - 1列已经排好且第i列不摆任何瓷砖的方案数

f[i][1]:前i - 1列已经排好且第i列 上方 的瓷砖铺好的方案数

f[i][2]:前i - 1列已经排好且第i列 全部 的瓷砖铺好的方案数

f[i][3]:前i - 1列已经排好且第i列 下方 的瓷砖铺好的方案数

状态属性：方案数

状态转移

f[i][0] = f[i - 1][2];

f[i][1] = f[i - 1][0] + f[i - 1][3];

f[i][2] = f[i - 1][0] + f[i - 1][1] + f[i - 1][2] + f[i - 1][3];

f[i][3] = f[i - 1][1] + f[i - 1][0];

初始化: f[0][3] = 1;

class Solution {
public:
    const int mod = 1e9 + 7;
    int numTilings(int n) {
        vector<vector<long long>> f(n + 1, vector<long long>(4, 0));
        f[0][2] = 1;
        for(int i = 1; i <= n; i ++){
            f[i][0] = f[i - 1][2];
            f[i][1] = (f[i - 1][0] + f[i - 1][3]) % mod;
            f[i][2] = (((f[i - 1][0] + f[i - 1][1]) % mod + f[i - 1][2]) % mod + f[i - 1][3]) % mod;
            f[i][3] = (f[i - 1][1] + f[i - 1][0]) % mod;
        }
        return f[n][2] % mod;
    }
};