Problem Description

The "Domino and Tromino Tiling" problem asks you to count the number of ways to completely cover a 2 x n board using two types of tiles:

• Domino: A 2 x 1 tile (can be placed vertically or horizontally).
• Tromino: An "L" shaped tile that covers three squares in an L pattern.

The tiles can be rotated and used any number of times. The board must be fully covered (no gaps or overlaps). The result should be returned modulo 10⁹ + 7.

Constraints:

• 1 ≤ n ≤ 1000
• Each tiling must use the tiles to cover the board exactly once, with no overlaps or uncovered squares.

Thought Process

The first instinct might be to try all possible placements of dominoes and trominoes recursively for each position on the board, but this quickly becomes infeasible as n grows large due to the exponential number of possibilities.

Instead, we look for a pattern or recurrence relation that allows us to build up the solution for larger boards from smaller boards. This is a classic application for dynamic programming, where we store solutions to subproblems and reuse them to solve bigger problems efficiently.

The key is to realize that the number of ways to tile a board of length n depends on how we fill the last few columns, and that we can relate the solution for n to solutions for smaller values of n.

Solution Approach

We use dynamic programming to solve this problem efficiently. Let dp[n] represent the number of ways to tile a 2 x n board.

• Base Cases:
  • dp[0] = 1: An empty board has one way to be tiled (do nothing).
  • dp[1] = 1: Only one vertical domino fits.
  • dp[2] = 2: Two vertical dominoes or two horizontal dominoes.
• Recurrence Relation:

  For n >= 3, to fill the last column(s), we have these options:

  1. Place a vertical domino in the last column:
     This leaves a 2 x (n-1) board, so dp[n-1] ways.
  2. Place two horizontal dominoes in the last two columns:
     This leaves a 2 x (n-2) board, so dp[n-2] ways.
  3. Place a tromino covering the last two columns and one cell from the third-to-last column (two possible orientations):
     Each orientation leaves a 2 x (n-3) board, so 2 * dp[n-3] ways.

  Therefore, the recurrence is:

  dp[n] = dp[n-1] + dp[n-2] + 2 * dp[n-3]

• Implementation:
  • Use a DP array to store values up to n.
  • Iterate from 3 to n, applying the recurrence and taking results modulo 10⁹+7.

Example Walkthrough

Let's walk through the solution for n = 4:

• Base cases:
  • dp[0] = 1
  • dp[1] = 1
  • dp[2] = 2
• Compute dp[3]:
  • dp[3] = dp[2] + dp[1] + 2 * dp[0] = 2 + 1 + 2*1 = 5
• Compute dp[4]:
  • dp[4] = dp[3] + dp[2] + 2 * dp[1] = 5 + 2 + 2*1 = 9

So, for n=4, there are 9 ways to tile the board.

At each step, we use previously computed values, making the process efficient and avoiding redundant calculations.

Time and Space Complexity

• Brute-force:
  • Without DP, trying all tile placements recursively leads to exponential time: O(3^n).
• Dynamic Programming:
  • We fill an array of size n+1 in a single loop.
  • Each step is O(1), so total time is O(n).
  • Space complexity is O(n) for the DP array (can be reduced to O(1) if only the last three values are kept).

Summary

The Domino and Tromino Tiling problem is elegantly solved using dynamic programming by recognizing the recurrence relation that ties together solutions to smaller subproblems. By building up the answer for larger boards from the answers to smaller boards, we achieve an efficient solution with linear time and space complexity. The key insight is understanding how each type of tile can be placed and how that affects the remaining board, allowing us to avoid redundant work and arrive at the answer efficiently.

Code Implementation

MOD = 10**9 + 7

def numTilings(n):
    if n == 0: return 1
    if n == 1: return 1
    if n == 2: return 2
    dp = [0] * (n + 1)
    dp[0], dp[1], dp[2] = 1, 1, 2
    for i in range(3, n + 1):
        dp[i] = (dp[i-1] + dp[i-2] + 2 * dp[i-3]) % MOD
    return dp[n]
      

class Solution {
public:
    int numTilings(int n) {
        const int MOD = 1e9+7;
        if (n == 0) return 1;
        if (n == 1) return 1;
        if (n == 2) return 2;
        vector<long long> dp(n+1, 0);
        dp[0] = 1; dp[1] = 1; dp[2] = 2;
        for (int i = 3; i <= n; ++i) {
            dp[i] = (dp[i-1] + dp[i-2] + 2 * dp[i-3]) % MOD;
        }
        return (int)dp[n];
    }
};
      

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

var numTilings = function(n) {
    const MOD = 1e9 + 7;
    if (n === 0) return 1;
    if (n === 1) return 1;
    if (n === 2) return 2;
    let dp = new Array(n+1).fill(0);
    dp[0] = 1; dp[1] = 1; dp[2] = 2;
    for (let i = 3; i <= n; i++) {
        dp[i] = (dp[i-1] + dp[i-2] + 2 * dp[i-3]) % MOD;
    }
    return dp[n];
};