We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Domino and Tromino Tiling

Number: 806

Difficulty: Medium

Paid? No

Companies: Google, Adobe, Amazon

Problem Description

Given a 2 x n board and two types of tiles—a 2 x 1 domino and a tromino (an L-shaped tile that covers three squares)—calculate the number of ways to completely tile the board. Tiles can be rotated and every square must be covered. Two tilings are different if there exists at least one pair of adjacent squares that in one tiling are covered by a single tile and in the other tiling are not.

Key Insights

  • The problem is solved via Dynamic Programming.
  • Use a recurrence relation based on tiling the board column by column.
  • Base cases include small boards (n = 0, 1, 2).
  • The recurrence relation derived is: dp[i] = dp[i-1] + 2 * dp[i-2] + dp[i-3] for i ≥ 3.
  • The answer is computed modulo 10^9+7 due to possible large values.

Space and Time Complexity

Time Complexity: O(n) because we compute dp[0] to dp[n] in one loop. Space Complexity: O(n) if using an array for dp; can be reduced to O(1) by keeping only last three values.

Solution

We solve this problem using dynamic programming by establishing a recurrence relation. Let dp[i] represent the number of ways to tile a 2 x i board. The base cases are:

  • dp[0] = 1 (an empty board)
  • dp[1] = 1 (only one way using a vertical domino)
  • dp[2] = 2 (either two vertical dominoes or two horizontal dominoes)

For i ≥ 3, consider:

  • Adding a vertical domino to a tiling of a 2 x (i-1) board (contributes dp[i-1]).
  • Adding two horizontal dominoes to a tiling of a 2 x (i-2) board (contributes dp[i-2]).
  • The tromino placement can cover three cells in an L shape; there are two orientations that contribute, and they depend on the tiling of a 2 x (i-3) board (contributes dp[i-3]).

Putting these contributions together, the recurrence becomes: dp[i] = dp[i-1] + 2 * dp[i-2] + dp[i-3]

This recurrence correctly produces dp[3] = dp[2] + 2*dp[1] + dp[0] = 2 + 2 + 1 = 5, matching the expected result for n = 3.

We use this recurrence iteratively (or with state optimization) and take modulo 10^9+7 at each step.

Code Solutions

# Python solution for Domino and Tromino Tiling
MOD = 10**9 + 7

def numTilings(n):
    # Base cases
    if n == 0:
        return 1
    if n == 1:
        return 1
    if n == 2:
        return 2

    # dp[i] will hold the number of tilings for a 2 x i board
    dp = [0] * (n + 1)
    dp[0], dp[1], dp[2] = 1, 1, 2

    # Fill dp table using the derived recurrence relation.
    for i in range(3, n + 1):
        dp[i] = (dp[i-1] + 2 * dp[i-2] + dp[i-3]) % MOD
    return dp[n]

# Example usage:
print(numTilings(3))  # Expected output: 5
← Back to All Questions