How do you solve Domino and Tromino Tiling?

Use a DP array dp where dp[i] represents the number of ways to tile a 2 x i board. Initialize base cases for dp[0], dp[1], and dp[2]. For i >= 3, compute dp[i] = 2 * dp[i-1] + dp[i-3], taking modulo 10^9 + 7 to handle large numbers. Return dp[n] as the final answer.

Domino and Tromino Tiling

Q: What is the time complexity of Domino and Tromino Tiling?

O(n). The algorithm computes dp values from 0 up to n once, each in constant time, resulting in linear time complexity.

Q: What pattern does Domino and Tromino Tiling use?

The Pattern: Dynamic Programming (Linear Recurrence with State Compression) The Heuristic: When counting combinatorial configurations with overlapping subproblems and complex piece placements, identify a recurrence that relates the current state to a fixed number of previous states, enabling efficient bottom-up computation.

Medium Dynamic Programming

Problem

Given an integer n, return the number of ways to tile a 2 x n board using 2 x 1 dominoes and L-shaped trominoes, modulo 10^9 + 7.

1 ≤ n ≤ 1000

Example

Input: n = 3

Output: 5

The possible tilings for a 2 x 3 board are: 1. Three vertical dominoes. 2. One horizontal domino on top row and two vertical dominoes below. 3. One horizontal domino on bottom row and two vertical dominoes above. 4. Two horizontal dominoes stacked. 5. One L-shaped tromino and one vertical domino. The algorithm uses a DP array to count ways for smaller boards and builds up to n using the recurrence dp[i] = 2 * dp[i-1] + dp[i-3].

Approach

Straightforward Solution

A brute-force approach would try all possible placements recursively, enumerating all tilings, which is exponential and infeasible for large n.

Core Observation

The number of ways to tile a 2 x n board depends on the ways to tile smaller boards, with the key insight that placing a vertical domino or tromino affects the board differently, leading to a recurrence involving dp[i-1] and dp[i-3].

Path to Optimal

Preview

Recognizing the problem as a counting problem with overlapping subproblems suggests dynamic programming…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a DP array dp where dp[i] represents the number of ways to tile a 2 x i board. Initialize base cases for dp[0], dp[1], and dp[2]…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm computes dp values from 0 up to n once, each in constant time, resulting in linear time complexity.

Space

O(n)

The dp array stores n+1 integers, each representing the count of tilings for boards of length up to n, which is necessary to avoid recomputation.

Pattern Spotlight

Dynamic Programming (Linear Recurrence with State Compression)

When counting combinatorial configurations with overlapping subproblems and complex piece placements, identify a recurrence that relates the current state to a fixed number of previous states, enabling efficient bottom-up computation.

Solution

Python

1class Solution:
2    def numTilings(self, n: int) -> int:
3        MOD = 10**9 + 7
4
5        if n == 1:
6            return 1
7
8        if n == 2:
9            return 2
10
11        dp = [0] * (n + 1)
12        dp[0] = 1
13        dp[1] = 1
14        dp[2] = 2
15
16        for i in range(3, n + 1):
17            dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD
18
19        return dp[n]

Step-by-Step Solution

Handle Base Cases for Small Board Lengths

5if n == 1:
6    return 1
8if n == 2:
9    return 2

Objective

To return immediate results for trivial board lengths where the number of tilings is known directly.

Key Insight

For n=1 and n=2, the number of tilings is small and can be enumerated manually. Handling these cases separately avoids unnecessary DP computation and sets the foundation for the recurrence to build upon.

Interview Quick-Check

Core Logic

Returning known results for n=1 and n=2 prevents invalid DP indexing and provides correct base values.

State & Boundaries

Base cases ensure the DP recurrence has valid starting points for indices dp[0], dp[1], and dp[2].

Initialize DP Array with Base Values

To set up the DP array and assign initial counts for the smallest board lengths.

Compute Number of Tilings Using Recurrence Relation

To iteratively compute the number of tilings for boards of length 3 to n using the derived recurrence.

Return Final Computed Result

To output the total number of tilings for the full board length n.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 17 Critical

dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD

Compute dp[i] using the recurrence and modulo operation.

The recurrence dp[i] = 2 * dp[i-1] + dp[i-3] captures all tilings by extending smaller boards with dominoes and trominoes, and modulo ensures results stay within integer limits.

Line 12 Critical

dp[0] = 1

Set dp[0] to 1 representing the empty board.

An empty board has one valid tiling (doing nothing), which serves as the base case for the recurrence.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

Why does the recurrence dp[i] = 2 * dp[i-1] + dp[i-3] correctly count all tilings?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Domino and Tromino Tiling from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Domino and Tromino Tiling drill

or drill a free problem

1	`class Solution:`
2	`def numTilings(self, n: int) -> int:`
3	`MOD = 10**9 + 7`
4
5	`if n == 1:`
6	`return 1`
7
8	`if n == 2:`
9	`return 2`
10
11	`dp = [0] * (n + 1)`
12	`dp[0] = 1`
13	`dp[1] = 1`
14	`dp[2] = 2`
15
16	`for i in range(3, n + 1):`
17	`dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD`
18
19	`return dp[n]`

5	`if n == 1:`
6	`return 1`
8	`if n == 2:`
9	`return 2`