algo-aha

瓷砖铺满2xN格子的方式数

• https://leetcode.com/problems/domino-and-tromino-tiling/

用一字型两格或L字型三格的瓷砖铺满2xN格子的方式数。

int numTilings(int N) {
    // 两个相互依赖的递推式：设d[i]表示铺满2*i格子的方式数，t[i]表示缺右上角或右下角铺满2*i-1格子的方式数
    // d[i] = d[i-1] /* 一竖 */ + d[i-2] /* 两横 */ + 2 * t[i-1] /*两种不同朝向的L型*/
    // t[i] = t[i-1] /* 一横 */ + d[i-2] /* 一个L型 */
    // 初始 d[1]=1, d[2]=2, t[1]=0, t[2]=1（虽然有缺右上角或右下角两种情况，但对确定的缺角情况只有一种L型）
    const int MOD = 1e9 + 7;
    vector<int> d(N + 1, 0), t(N + 1, 0);
    d[1] = 1, d[2] = 2, t[1] = 0, t[2] = 1;
    for (int i = 3; i <= N; i++) {
        d[i] = (d[i-1] + d[i-2] + 2l * t[i-1]) % MOD;
        t[i] = (t[i-1] + d[i-2]) % MOD;
    }
    return d[N];
}