Domino and Tromino Tiling

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<sup>9</sup> + 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

# Dynamic Programming Solution for Tiling a 2 x n Board

This problem asks us to find the number of ways to tile a 2 x n board using 2 x 1 dominoes and trominoes (L-shaped tiles). Since the number of ways can be very large, we need to return the result modulo 10^9 + 7.

## Naive Approach (Recursion)

A naive approach would be to use recursion. We can define a recursive function that takes the length `n` as input and returns the number of ways to tile the board. However, this approach would have exponential time complexity due to overlapping subproblems.

## Optimal Solution (Dynamic Programming)

We can use dynamic programming to solve this problem efficiently. Let's define two arrays, `dp[i]` and `dp_incomplete[i]`:

- `dp[i]` represents the number of ways to completely tile a 2 x `i` board.
- `dp_incomplete[i]` represents the number of ways to tile a 2 x `i` board with one square uncovered (either the top right or bottom right square).

We can derive the following recurrence relations:

- `dp[i] = dp[i-1] + dp[i-2] + 2 * dp_incomplete[i-1]`
- `dp_incomplete[i] = dp_incomplete[i-1] + dp[i-2]`

The base cases are:

- `dp[0] = 1` (empty board has one way to tile it)
- `dp[1] = 1` (one vertical domino)
- `dp_incomplete[0] = 0`
- `dp_incomplete[1] = 1`

Here's the Python code:

```python
MOD = 10**9 + 7

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

Big(O) Runtime Analysis

The time complexity of this dynamic programming solution is O(n) because we iterate from 3 to n once to fill the dp and dp_incomplete arrays.

Big(O) Space Usage Analysis

The space complexity is O(n) because we use two arrays, dp and dp_incomplete, each of size n + 1 to store the intermediate results. We can further optimize it to O(1) space by only storing the last two dp values and the last dp_incomplete value.

Here's the optimized code with O(1) space complexity:

MOD = 10**9 + 7

def numTilings(n: int) -> int:
    if n <= 2:
        return n

    dp0 = 1
    dp1 = 1
    dp2 = 2
    dp_incomplete1 = 1
    dp_incomplete2 = 2

    for i in range(3, n + 1):
        dp_i = (dp2 + dp1 + 2 * dp_incomplete2) % MOD
        dp_incomplete_i = (dp_incomplete2 + dp1) % MOD

        dp0 = dp1
        dp1 = dp2
        dp2 = dp_i
        dp_incomplete1 = dp_incomplete2
        dp_incomplete2 = dp_incomplete_i

    return dp2

Edge Cases

1. n = 1: The board is 2 x 1. There is only one way to tile it using a vertical domino.
2. n = 2: The board is 2 x 2. There are two ways to tile it: two vertical dominoes or two horizontal dominoes.
3. n = 3: The board is 2 x 3. There are five ways to tile it.

These base cases are handled correctly in the provided code.

Explanation of the Formula

• dp[i] = dp[i-1] + dp[i-2] + 2 * dp_incomplete[i-1]
  • dp[i-1] represents placing a vertical domino at the end of the 2 x i board.
  • dp[i-2] represents placing two horizontal dominoes at the end of the 2 x i board.
  • 2 * dp_incomplete[i-1] represents placing a tromino at the end of the board. We multiply by 2 because there are two possible orientations for the tromino.
• dp_incomplete[i] = dp_incomplete[i-1] + dp[i-2]
  • dp_incomplete[i-1] represents adding a vertical domino to the incomplete board.
  • dp[i-2] represents adding a tromino to the board to make it incomplete.

By using dynamic programming, we efficiently calculate the number of ways to tile the 2 x n board, ensuring that we handle all possible cases and avoid redundant calculations.