Domino and Tromino Tiling

A brute-force recursive approach would explore every possible way to place tiles, which is highly inefficient. We can significantly improve this by using memoization to store the results of subproblems, which turns the solution into a top-down dynamic programming approach. We define two states: one for a fully tiled 2 x n board and another for a 2 x n board with a single corner cell in the last column left uncovered. By deriving recurrence relations for these states, we can solve the problem recursively while storing intermediate results to avoid redundant calculations.

1. Define two recursive functions, f(n) and p(n):
   • f(n): returns the number of ways to fully tile a 2 x n board.
   • p(n): returns the number of ways to tile a 2 x n board with one of the corners in column n uncovered (a 'partial' tiling). By symmetry, the number of ways is the same whether the top or bottom corner is uncovered.
2. Establish the recurrence relations:
   • To get a fully tiled 2 x n board (f(n)):
     • Start with a fully tiled 2 x (n-1) board and add a vertical domino. This gives f(n-1) ways.
     • Start with a fully tiled 2 x (n-2) board and add two horizontal dominoes. This gives f(n-2) ways.
     • Start with a partially tiled 2 x (n-1) board (top corner uncovered) and add an L-tromino to complete the board. This gives p(n-1) ways.
     • Start with a partially tiled 2 x (n-1) board (bottom corner uncovered) and add an L-tromino. This also gives p(n-1) ways.
     • So, f(n) = f(n-1) + f(n-2) + 2 * p(n-1).
   • To get a partially tiled 2 x n board (p(n)):
     • Start with a fully tiled 2 x (n-2) board and add an L-tromino that leaves a corner of column n uncovered. This gives f(n-2) ways.
     • Start with a 2 x (n-1) board with the opposite corner uncovered and add a horizontal domino. This gives p(n-1) ways.
     • So, p(n) = p(n-1) + f(n-2).
3. Define the base cases:
   • f(0) = 1 (one way to tile a 2x0 board: do nothing).
   • f(1) = 1 (one vertical domino).
   • p(0) = 0, p(1) = 0 (no way to have these partial shapes for n=0 or n=1).
4. Implement the recursive functions using memoization (e.g., arrays memo_f and memo_p) to store and reuse the results of subproblems, avoiding recomputation. All calculations should be done modulo 10^9 + 7.

Let f(n) be the number of ways to fully tile a 2 x n board, and p(n) be the number of ways to tile a 2 x (n-1) board plus one cell in column n (creating a shape with a single uncovered cell in the corner of the 2 x n area). By analyzing the ways to place the last tile(s), we can establish recurrence relations.

• For a fully tiled 2 x n board (f(n)): We can arrive at this state from:

  1. A fully tiled 2 x (n-1) board by adding a vertical domino.
  2. A fully tiled 2 x (n-2) board by adding two horizontal dominoes.
  3. A partially tiled 2 x (n-1) board by adding an L-tromino to fill the remaining shape. Since there are two symmetric partial states (top or bottom corner uncovered), this adds 2 * p(n-1) ways. The recurrence is: f(n) = f(n-1) + f(n-2) + 2 * p(n-1).

• For a partially tiled 2 x n board (p(n)): We can arrive at this state from:

  1. A fully tiled 2 x (n-2) board by adding an L-tromino.
  2. A partially tiled 2 x (n-1) board (with the opposite corner uncovered) by adding a horizontal domino. The recurrence is: p(n) = p(n-1) + f(n-2).

We use two memoization arrays, memo_f and memo_p, to store the computed values and avoid re-computation. The final answer is f(n).

class Solution {
    long MOD = 1_000_000_007;
    long[] memo_f;
    long[] memo_p;

    public int numTilings(int n) {
        if (n <= 2) {
            return n;
        }
        memo_f = new long[n + 1];
        memo_p = new long[n + 1];
        return (int) f(n);
    }

    // Ways to fully tile a 2 x i board
    private long f(int i) {
        if (i == 0) return 1;
        if (i == 1) return 1;
        if (i == 2) return 2;
        if (memo_f[i] != 0) return memo_f[i];

        memo_f[i] = (f(i - 1) + f(i - 2) + 2 * p(i - 1)) % MOD;
        return memo_f[i];
    }

    // Ways to tile a 2 x (i-1) board with one extra cell in column i
    private long p(int i) {
        if (i <= 1) return 0;
        if (i == 2) return 1;
        if (memo_p[i] != 0) return memo_p[i];

        memo_p[i] = (p(i - 1) + f(i - 2)) % MOD;
        return memo_p[i];
    }
}