多米诺和托米诺平铺

Leetcode-790-多米诺和托米诺平铺

分析

错位相减法优化状态转移方程。

状态转移方程：f[i]=f[i−1]+f[i−2]+2​i=0​∑​i−3​​f[i],(1)

f[i−1]=f[i−2]+f[i−3]+2​i=0​∑​i−4​​f[i],(2)

由$(2)-(1)$并整理得：$f[i]=2f[i-1]+f[i-3]$。

实现

class Solution {
    typedef long long LL;
    const int M = 1e9 + 7;
    int f[1010];
public:
    int numTilings(int n) {
        if (f[n] != 0) return f[n];
        if (n == 0 || n == 1) return 1;

        int res = 0;
        if (n >= 1) res = (res + (LL)2 * numTilings(n - 1)) % M;
        if (n >= 3) res = (res + numTilings(n - 3)) % M;
        return f[n] = res;
    }
};