#790

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Domino and Tromino Tiling

Calculate the number of ways to tile a 2xN board using dominoes and trominoes with precise state transitions.

Problem Statement

You are given a 2xN board and two types of tiles: a domino (2x1) and an L-shaped tromino. Tiles can be rotated, and every square on the board must be fully covered without overlap.

Return the total number of distinct ways to tile the 2xN board. Since the number may be very large, provide the answer modulo 10^9 + 7. Two tilings are different if there exists a pair of 4-directionally adjacent squares covered differently between tilings.

Examples

Example 1

Input: n = 3

Output: 5

The five different ways are shown above.

Example 2

Input: n = 1

Output: 1

Example details omitted.

Constraints

1 <= n <= 1000

Solution Approach

Define Dynamic Programming States

Let dp[n] represent the number of valid tilings for a 2xN board. Introduce auxiliary states to capture incomplete or partial tile placements, such as one row filled and one row partially filled, to correctly account for tromino placements.

Establish State Transitions

For each n, calculate dp[n] using previous states: adding a vertical domino extends dp[n-1], adding two horizontal dominoes or a tromino covers dp[n-2] or dp[n-3] respectively. Carefully combine subproblem counts to maintain correctness without double-counting overlapping configurations.

Apply Modulo and Iterate

Iterate from 1 to N, updating dp states while taking modulo 10^9 + 7 at every step. This prevents integer overflow and ensures results fit within constraints. Return dp[N] as the total number of tilings.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(N) since each dp[n] depends on a fixed number of previous states, and space complexity is O(N) for storing all states. Optimizations can reduce space to O(1) by keeping only the last three states.

What Interviewers Usually Probe

Look for efficient dynamic programming over naive recursion with exponential blowup.
Expect correct handling of partial row states to accommodate L-shaped trominoes.
Check whether modulo arithmetic is applied to prevent overflow on large N.

Common Pitfalls or Variants

Common pitfalls

Ignoring the partial states caused by trominoes and double-counting configurations.
Forgetting to apply modulo 10^9 + 7 at each dp update.
Assuming only domino placements without considering rotated tromino contributions.

Follow-up variants

Tiling a 3xN board with dominoes and trominoes, requiring additional state dimensions.
Counting tilings with forbidden placements or obstacles on the 2xN board.
Tiling with additional tile shapes, increasing the number of states to track.

FAQ

What is the primary pattern used in Domino and Tromino Tiling?

The problem follows state transition dynamic programming, where each dp[n] depends on previous board states to account for domino and tromino placements.

How do tromino placements affect the DP states?

Trominoes introduce partial row states, so auxiliary DP arrays or variables are needed to track configurations where one row is partially filled.

Why is modulo 10^9 + 7 necessary?

Because the number of tilings grows exponentially with N, modulo arithmetic prevents integer overflow and keeps computations within constraints.

Can space complexity be reduced for this problem?

Yes, by keeping only the last three dp states, you can reduce space complexity from O(N) to O(1) without affecting correctness.

What common mistakes do candidates make?

Candidates often forget to handle partial states for trominoes, apply modulo operations incorrectly, or double-count overlapping configurations.

terminal

Solution

Solution 1: Dynamic Programming

First, we need to understand the problem. The problem is essentially asking us to find the number of ways to tile a $2 \times n$ board, where each square on the board can only be covered by one tile.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def numTilings(self, n: int) -> int:
        f = [1, 0, 0, 0]
        mod = 10**9 + 7
        for i in range(1, n + 1):
            g = [0] * 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 f[0]

Continue Practicing

#788 rotated digits #792 number of matching subsequences #787 cheapest flights within k stops