790. Domino and Tromino Tiling

Description

image-20210825135307308

image-20210825135319048

Solution

Check the dp state illustrated in picture

image-20210825140239577

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    static const int MOD = 1E9 + 7;
public:
    int numTilings(int n) {
        if(n == 1)
            return 1;
        vector<vector<long long>> dp(2, vector<long long>(1+n,0));
        dp[0][1] = 1;
        dp[1][2] = 2;
        dp[0][2] = 2;
        for(int i = 3; i <= n; i++){
            dp[0][i] = (dp[0][i-1] + dp[1][i-1] + dp[0][i-2])%MOD;
            dp[1][i] = (dp[0][i-2] * 2 + dp[1][i-1])%MOD;
        }
        return dp[0][n] % MOD;
    }
};