# Domino and Tromino Tiling
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/domino-and-tromino-tiling)
Canonical: https://scaleengineer.com/dsa/problems/domino-and-tromino-tiling
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Companies:** [WinZO](https://scaleengineer.com/companies/winzo)
---
## Problem
You have two types of tiles: a `2 x 1` domino shape and a tromino shape. You may rotate these shapes.

![](https://assets.glich.co/dsa/domino-and-tromino-tiling/image0.jpg) 

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** `109 + 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:**

![](https://assets.glich.co/dsa/domino-and-tromino-tiling/image1.jpg) 

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

**Example 2:**

**Input:** n = 1
**Output:** 1

**Constraints:**

* `1 <= n <= 1000`

# Approaches
## Top-Down Dynamic Programming
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.
**Time:** O(N) - Each state `f(i)` and `p(i)` for `i` from 1 to `n` is computed once. · **Space:** O(N) - For the memoization arrays and the recursion stack depth.
**Pros:** Relatively intuitive to derive from the problem's recursive nature.; Correctly solves the problem within the time limits.
**Cons:** May lead to a stack overflow for very large `n` if the recursion depth limit is exceeded.; Generally has higher constant-factor overhead compared to the iterative bottom-up approach due to function calls.
### Explanation
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)`.

```java
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];
    }
}
```
### Algorithm
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`.

## Bottom-Up Dynamic Programming
This approach converts the recursive solution into an iterative one, which is often more efficient by eliminating recursion overhead. We can use the same recurrence relations but calculate the values iteratively, from the base cases up to `n`. A key insight is that the two recurrences for the fully tiled and partially tiled states can be algebraically combined into a single, simpler recurrence. This eliminates the need for the helper DP state, simplifying the implementation.
**Time:** O(N) - We iterate from 3 to `n` once. · **Space:** O(N) - To store the dynamic programming array.
**Pros:** More efficient than the top-down approach due to the removal of recursion overhead.; The simplified recurrence is cleaner and easier to implement.
**Cons:** Requires O(N) space, which is not optimal.
### Explanation
Instead of recursion, we can build the solution from the ground up. We can find a direct recurrence for `f(n)`, the number of ways to fully tile a `2 x n` board. By manipulating the two recurrences from the previous approach:

1. `f(n) = f(n-1) + f(n-2) + 2*p(n-1)`
2. `f(n-1) = f(n-2) + f(n-3) + 2*p(n-2)`

Subtracting (2) from (1) gives:
`f(n) - f(n-1) = f(n-1) - f(n-3) + 2 * (p(n-1) - p(n-2))`

From the second original recurrence, `p(n) = p(n-1) + f(n-2)`, we have `p(n-1) - p(n-2) = f(n-3)`. Substituting this in:
`f(n) - f(n-1) = f(n-1) - f(n-3) + 2*f(n-3)`
`f(n) = 2*f(n-1) + f(n-3)`

This simplified recurrence only depends on the previous values of `f`. We can use a single DP array to store these values.

```java
class Solution {
    public int numTilings(int n) {
        if (n <= 2) {
            return n;
        }
        long MOD = 1_000_000_007;
        long[] dp = new long[n + 1];
        
        // Base cases
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        
        for (int i = 3; i <= n; i++) {
            dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD;
        }
        
        return (int) dp[n];
    }
}
```
### Algorithm
1. Simplify the recurrence relations derived in the top-down approach. By algebraic manipulation, the two recurrences `f(n) = f(n-1) + f(n-2) + 2*p(n-1)` and `p(n) = p(n-1) + f(n-2)` can be combined into a single recurrence involving only `f`:
   `f(n) = 2 * f(n-1) + f(n-3)`.
2. Create a DP array, say `dp`, of size `n+1` to store the number of ways to tile a `2 x i` board for `i` from 0 to `n`.
3. Initialize the base cases for the DP array based on the problem:
   - `dp[0] = 1`
   - `dp[1] = 1`
   - `dp[2] = 2`
4. Iterate from `i = 3` to `n`, filling the `dp` array using the simplified recurrence relation: `dp[i] = (2 * dp[i-1] + dp[i-3]) % MOD`.
5. The final answer is `dp[n]`.

## Space-Optimized Bottom-Up DP
We can further optimize the bottom-up DP approach in terms of space. Observing the recurrence `f(n) = 2 * f(n-1) + f(n-3)`, we see that the calculation for `f(n)` only depends on the three preceding terms `f(n-1)`, `f(n-2)`, and `f(n-3)`. Therefore, we don't need to store the entire DP table. We can use a constant number of variables to keep track of only the last few values, reducing the space complexity from O(N) to O(1).
**Time:** O(N) - A single loop from 3 to `n` is performed. · **Space:** O(1) - We only use a few variables to store the previous states, regardless of `n`.
**Pros:** Extremely efficient in terms of space, using only O(1) extra space.; Maintains the efficient O(N) time complexity.
**Cons:** The logic for updating the state variables can be slightly tricky to get right compared to using a full array.
### Explanation
This approach builds upon the simplified recurrence `f(n) = 2 * f(n-1) + f(n-3)`. Since we only need a fixed number of previous states to compute the next one, we can discard older states that are no longer needed. We maintain three variables that represent `f(i-3)`, `f(i-2)`, and `f(i-1)` and use them to compute `f(i)`. Then, we update these variables for the next iteration. This is a standard technique for optimizing the space complexity of DP problems with limited state dependencies.

```java
class Solution {
    public int numTilings(int n) {
        if (n <= 2) {
            return n;
        }
        long MOD = 1_000_000_007;
        
        // Initialize variables for the last three values
        // a = f(i-3), b = f(i-2), c = f(i-1)
        long a = 1; // f(0)
        long b = 1; // f(1)
        long c = 2; // f(2)
        
        for (int i = 3; i <= n; i++) {
            long current = (2 * c + a) % MOD;
            a = b;
            b = c;
            c = current;
        }
        
        return (int) c;
    }
}
```
### Algorithm
1. Use the simplified recurrence `f(n) = 2 * f(n-1) + f(n-3)`.
2. Notice that to compute `f(i)`, we only need the values of `f(i-1)` and `f(i-3)`.
3. Instead of an entire array, use a few variables to keep track of the last three values needed: `f(i-1)`, `f(i-2)`, and `f(i-3)`.
4. Initialize variables to represent the base cases, e.g., `a = f(0)=1`, `b = f(1)=1`, `c = f(2)=2`.
5. Iterate from `i = 3` to `n`. In each iteration:
   - Calculate the current value: `current = (2 * c + a) % MOD`.
   - Update the variables for the next iteration: `a` becomes `b`, `b` becomes `c`, and `c` becomes `current`.
6. After the loop, the variable representing the last computed value (`c`) holds the result for `f(n)`.

## Matrix Exponentiation
For problems that can be described by a linear recurrence relation, matrix exponentiation provides an asymptotically faster solution. The recurrence `f(n) = 2*f(n-1) + f(n-3)` is linear. We can represent the state transition from `[f(n-1), f(n-2), f(n-3)]` to `[f(n), f(n-1), f(n-2)]` as a matrix multiplication. To find `f(n)`, we can raise this transformation matrix to the power of `n` (or a related power like `n-2`). Using binary exponentiation (also known as exponentiation by squaring), we can compute the matrix power in logarithmic time, making this the most efficient approach for large `n`.
**Time:** O(log N) - Due to the binary exponentiation algorithm for matrices. Matrix multiplication takes constant time as the size is fixed. · **Space:** O(1) - The space used for matrices is constant (3x3).
**Pros:** Asymptotically the fastest approach with O(log N) time complexity.; Very effective for extremely large values of `n` where an O(N) solution would be too slow.
**Cons:** More complex to understand and implement compared to the DP approaches.; The constant factor for matrix multiplication is larger, so for small `n` (like `n <= 1000`), the O(N) DP approach might be practically faster.
### Explanation
The core idea is to use a matrix to represent the transitions of the recurrence `f(n) = 2*f(n-1) + f(n-3)`. We define a state vector `[f(n), f(n-1), f(n-2)]^T`. The transformation matrix `M` that advances this state by one step is:

```
| f(n)   |   | 2  0  1 | | f(n-1) |
| f(n-1) | = | 1  0  0 | | f(n-2) |
| f(n-2) |   | 0  1  0 | | f(n-3) |
```

To find `f(n)`, we start with a base state vector, like `[f(2), f(1), f(0)]^T`, and apply the transformation `n-2` times. This is equivalent to computing `M^(n-2)` and multiplying it by the initial vector. The power of a matrix can be calculated efficiently in `O(k^3 * log n)` time, where `k` is the matrix dimension (here, `k=3`).

```java
class Solution {
    long MOD = 1_000_000_007;

    public int numTilings(int n) {
        if (n <= 2) {
            return n;
        }

        long[][] M = {{2, 0, 1}, {1, 0, 0}, {0, 1, 0}};
        long[][] M_pow = matrixPower(M, n - 2);

        // Initial vector: [f(2), f(1), f(0)] = [2, 1, 1]
        long result = (M_pow[0][0] * 2 + M_pow[0][1] * 1 + M_pow[0][2] * 1) % MOD;
        return (int) result;
    }

    private long[][] matrixMultiply(long[][] A, long[][] B) {
        long[][] C = new long[3][3];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
                }
            }
        }
        return C;
    }

    private long[][] matrixPower(long[][] A, int pow) {
        long[][] res = new long[3][3];
        for (int i = 0; i < 3; i++) {
            res[i][i] = 1; // Identity matrix
        }
        long[][] P = A;
        while (pow > 0) {
            if ((pow & 1) == 1) {
                res = matrixMultiply(res, P);
            }
            P = matrixMultiply(P, P);
            pow >>= 1;
        }
        return res;
    }
}
```
### Algorithm
1. Express the linear recurrence `f(n) = 2*f(n-1) + f(n-3)` in matrix form.
2. Define a state vector `V_n = [f(n), f(n-1), f(n-2)]^T`.
3. Find the 3x3 transformation matrix `M` such that `V_n = M * V_{n-1}`.
   The matrix `M` is `[[2, 0, 1], [1, 0, 0], [0, 1, 0]]`.
4. The relation `V_n = M * V_{n-1}` implies `V_n = M^(n-2) * V_2`.
5. The initial state vector is `V_2 = [f(2), f(1), f(0)]^T = [2, 1, 1]^T`.
6. Implement a function to perform matrix multiplication for 3x3 matrices, with all calculations modulo `10^9 + 7`.
7. Implement a function to compute the matrix power `M^(n-2)` using the binary exponentiation (or exponentiation by squaring) algorithm. This takes `O(log n)` time.
8. Compute `M_pow = M^(n-2)`.
9. Multiply `M_pow` by the initial vector `V_2` to get the final state vector `V_n`.
10. The result is the first element of `V_n`, which is `f(n)`.

# Solutions
### Java

```java
class Solution {
public
  int numTilings(int n) {
    long[] f = {1, 0, 0, 0};
    int mod = (int)1 e9 + 7;
    for (int i = 1; i <= n; ++i) {
      long[] g = new long[4];
      g[0] = (f[0] + f[1] + f[2] + f[3]) % mod;
      g[1] = (f[2] + f[3]) % mod;
      g[2] = (f[1] + f[3]) % mod;
      g[3] = f[0];
      f = g;
    }
    return (int)f[0];
  }
}

```

### CPP

```cpp
class Solution {
public:
  const int mod = 1e9 + 7;
  int numTilings(int n) {
    long f[4] = {1, 0, 0, 0};
    for (int i = 1; i <= n; ++i) {
      long g[4] = {0, 0, 0, 0};
      g[0] = (f[0] + f[1] + f[2] + f[3]) % mod;
      g[1] = (f[2] + f[3]) % mod;
      g[2] = (f[1] + f[3]) % mod;
      g[3] = f[0];
      memcpy(f, g, sizeof(g));
    }
    return f[0];
  }
};

```

### Python

```python
class Solution:
    def numTilings(self, n: int) -> int: @ cache def dfs(i, j): if i > n or j > n: return 0 if i == n and j == n: return 1 ans = 0 if i == j: ans = (dfs(i + 2, j + 2) + dfs(i + 1, j + 1) + dfs(i + 2, j + 1) + dfs(i + 1, j + 2)) elif i > j: ans = dfs(i, j + 2) + dfs(i + 1, j + 2) else: ans = dfs(i + 2, j) + dfs(i + 2, j + 1) return ans % mod mod = 10 ** 9 + 7 return dfs(0, 0)

```