790. Domino and Tromino Tiling

Description

The problem involves finding the number of ways to tile a 2xN board using a combination of dominoes (2x1 or 1x2 tiles) and trominoes (an "L" shape covering a 2x2 area minus one 1x1 square). Given an integer n, you need to compute how many different ways you can completely cover a 2xN board.

Intuition

The problem can be approached using dynamic programming by considering the different ways to fill the last column or set of columns. We start by understanding the base cases and then extend the logic for larger boards by considering the different possible tiles that can cover the last few squares of the board.

Approach

1. Base Cases: - For n = 1, there's only one way to cover the board with a vertical domino. - For n = 2, there are two ways: two vertical dominoes or two horizontal dominoes. - For n = 3, there are five ways: combinations of dominoes and a tromino.
2. Dynamic Programming Transition: - For larger n, the number of ways to tile the board is determined by combining the solutions of smaller boards. The recurrence relation considers: - 2 * dp[i - 1]: This accounts for extending the board from a previously solved state using either a domino or a tromino. - dp[i - 3]: This accounts for using a tromino or a combination of dominoes to reach the current state.
3. Implementation: - Store the number of ways to tile boards of different lengths in a dp array. - Use the recurrence relation to fill out the dp array up to the given n. - Return the value stored for the 2xN board.

Complexity

Time Complexity:

O(n) because we iterate from 4 to n to fill out the dp array.

Space Complexity:

O(n) because we store the number of ways to tile boards of size 0 to n in the dp array.

Code

C++

class Solution {
public:
    int numTilings(int n) {
        int mod = 1e9 + 7;
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 5;

        vector dp(n + 1);
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 5;

        for (int i = 4; i <= n; i++) {
            dp[i] = (2 * dp[i - 1] + dp[i - 3]) % mod;
        }

        return dp[n];
    }
};

Python

class Solution:
    def numTilings(self, n: int) -> int:
        mod = 10**9 + 7
        if n == 1:
            return 1
        if n == 2:
            return 2
        if n == 3:
            return 5

        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1
        dp[2] = 2
        dp[3] = 5

        for i in range(4, n + 1):
            dp[i] = (2 * dp[i - 1] + dp[i - 3]) % mod

        return dp[n]

Java

class Solution {
    public int numTilings(int n) {
        int mod = 1000000007;
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 5;

        long[] dp = new long[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 5;

        for (int i = 4; i <= n; i++) {
            dp[i] = (2 * dp[i - 1] + dp[i - 3]) % mod;
        }

        return (int) dp[n];
    }
}

JavaScript

var numTilings = function (n) {
    let mod = 10 ** 9 + 7;
    let len = 4;
    let ways = new Array(len).fill(0);
    ways[0] = 1;
    ways[1] = 1;
    ways[2] = 2;
    if (n < len - 1) {
        return ways[n];
    }
    for (var i = len - 1; i <= n; i++) {
        ways[i % len] = (
            ways[(len + i - 1) % len] * 2
            +
            ways[(len + i - 3) % len]
        ) % mod;
    }
    return ways[(i - 1) % len];
};