790. Domino and Tromino Tiling

Problem Statement

Medium

You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.

Given an integer n, return the number of ways to tile an 2 x n board. Since the answer may be very large, return it modulo 10⁹ + 7.

In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.

Example 1:

Input: n = 3
Output: 5
Explanation: The five different ways are show above.

Example 2:

Input: n = 1
Output: 1

Constraints:

1 <= n <= 1000

C++

Source file

class Solution {
public:
    int numTilings(int n) {
        int mod=1e9+7;
        long long dp1 = 1, dp2 = 2, dp3 = 5, dp4;
        if(n<=3){
            switch(n){
                case 1: return dp1;
                case 2: return dp2;
                case 3: return dp3; 
            }
        }
        for (int i=4; i<=n; i++) {
            dp4 = (2* dp3 + dp1) % mod;
            dp1 = dp2;
            dp2 = dp3;
            dp3 = dp4;
        }
        return dp4;
    }
};

Java

Source file

class Solution {
    public int numTilings(int n) {
        int MOD = 1_000_000_007;
        long[] dp = new long[4];
        dp[0] = 1;
        dp[1] = 2;
        dp[2] = 5;
        if (n < 4)
            return (int) dp[n - 1];
        for (int i = 4; i <= n; i++) {
            dp[3] = (2 * dp[2] + dp[0]) % MOD;
            for (int j = 0; j < 3; j++)
                dp[j] = dp[j + 1];
        }
        return (int) dp[3];
    }
}