algoadvance

You have two types of tiles: a 2x1 domino shape, and a “L” tromino shape. You may rotate the tromino shapes.

Given an integer n, return the number of ways to tile an 2 x n board using these two types of tiles.

In a tiling, every square must be covered by a tile.

Return the answer modulo (10^9 + 7).

Clarifying Questions

  1. Q: Can we assume ( n ) is a non-negative integer? A: Yes, ( n ) will be a non-negative integer.

  2. Q: Do we need to consider rotations of domino and tromino? A: Yes, we need to consider all rotations/positions in which the tromino can be used.

  3. Q: Is there a well-defined base case for ( n = 0 )? A: For ( n = 0 ), the answer should be 1 since there’s one way to cover an empty board.

Strategy

We can use dynamic programming to solve this problem. We’ll define two states:

Recurrence Relations:

  1. Base cases:
    • dp[0] = 1 (1 way to cover an empty board)
    • dp[1] = 1 (1 way to cover a 2x1 board with a single domino)
  2. Recurrence for dp[i]:
    • Cover the last two columns entirely with vertical dominos: dp[i-2]
    • Cover the last two columns as the base of an “L” tromino shape in three different rotations: 2 * dpT[i-1]
    • Cover the last three columns with two “L” tromino shapes: dp[i-3]
  3. Recurrence for dpT[i]:
    • Join the uncovered cell with the cell to its left using a horizontal domino and consider the rest of the board fully covered: dp[i-2]
    • Complete the row with another “L” tromino: dpT[i-1]

Code

def numTilings(n: int) -> int:
    MOD = 10**9 + 7

    if n == 0:
        return 1
    if n == 1:
        return 1
    if n == 2:
        return 2  # Two ways: two vertical dominos or two horizontal dominos

    dp = [0] * (n + 1)
    dpT = [0] * (n + 1)

    dp[0] = 1
    dp[1] = 1
    dp[2] = 2

    dpT[2] = 1

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

    return dp[n] % MOD

# Example usage:
print(numTilings(3))  # Output: 5
print(numTilings(4))  # Output: 11

Time Complexity

The time complexity of this solution is ( O(n) ) because we are iterating through the range of n to fill the dp arrays. The space complexity is also ( O(n) ) due to the storage used for the dp and dpT arrays.

Try our interview co-pilot at AlgoAdvance.com