Domino and Tromino Tiling: Dynamic Programming on a Grid

You have a 2xN board and two types of tiles: dominoes that cover exactly two squares, and trominoes (L-shaped pieces) that cover exactly three squares. Given an integer n, return the number of ways to tile the entire 2xN board. Since the answer can be very large, return it modulo 10^9 + 7.

This is LeetCode 790: Domino and Tromino Tiling, and it is one of the cleanest examples of how to derive a DP recurrence by analyzing tile placements on a grid.

Why this problem matters

Most counting DP problems give you a recurrence that looks obvious once you see it. This one is different. The recurrence dp[i] = 2 * dp[i-1] + dp[i-3] is not something you would guess on the first try. You need to carefully reason about which tile placements lead to fully covered columns versus partially covered columns, and then collapse those observations into a single formula. That reasoning process is the real skill this problem teaches.

This problem also bridges two common DP categories. On one hand, it is a linear DP problem where you fill in a 1D array left to right. On the other hand, the tromino placements introduce "partial states" where one row extends further than the other. Learning to handle those partial states prepares you for harder tiling and grid problems where the boundary between filled and unfilled regions is irregular.

Once you see how the tromino creates a dependency on dp[i-3], you start recognizing similar patterns in other problems. Anytime a tile or move can reach back more than one step, the recurrence picks up extra terms. That insight transfers directly to problems like Climbing Stairs variants with larger step sizes and other combinatorial DP problems.

The approach

Define dp[i] as the number of ways to fully tile a 2xi board. The key insight is figuring out what happens when you extend from column i-1 to column i.

If column i-1 is fully tiled, you can place a single vertical domino to fill column i. That gives you dp[i-1] ways. You can also place two horizontal dominoes spanning columns i-1 and i, but that requires column i-1 to have been completed by the time you placed tiles up to column i-2. That effectively contributes dp[i-2] ways.

The tricky part is the tromino. An L-shaped tromino covers two cells in one column and one cell in the adjacent column. When you place a tromino at column i, it leaves a gap that can only be filled by placing another tromino in the mirrored orientation, and together they span three columns. Working through the algebra, every pair of tromino placements contributes dp[i-3] ways to the count.

Combining these observations and simplifying, the recurrence becomes:

• dp[0] = 1, dp[1] = 1, dp[2] = 2
• dp[i] = 2 * dp[i-1] + dp[i-3] for i >= 3

This can also be derived from the more general recurrence dp[i] = dp[i-1] + dp[i-2] + 2 * (dp[i-3] + dp[i-4] + ... + dp[0]), which telescopes down to dp[i] = 2 * dp[i-1] + dp[i-3].

Clean solution

def numTilings(n):
    MOD = 10**9 + 7
    if n == 1:
        return 1
    if n == 2:
        return 2

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

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

    return dp[n]

The solution fills a DP array from left to right in O(n) time. Each entry depends on at most two previous entries, making the recurrence cheap to evaluate.

Step-by-step walkthrough

The walkthrough traces the recurrence for a 2x5 board. At each step, the value of dp[i] is computed from 2 * dp[i-1] (covering the domino extensions) plus dp[i-3] (covering the tromino pair extensions). The sequence grows as 1, 1, 2, 5, 11, 24.

Notice how the dp[i-3] term is what separates this problem from a simple Fibonacci-like recurrence. Without trominoes, you would just have dp[i] = dp[i-1] + dp[i-2], which is the recurrence for Climbing Stairs. The tromino pairs reaching back three columns are what give the problem its distinctive character.

Complexity analysis

The DP table approach uses an array of size n + 1. Since the recurrence only looks back three positions, you can replace the array with three variables and reduce space to O(1). The time complexity remains O(n) either way, as you compute each entry once in a single pass.

The building blocks

1. Linear DP with fixed lookback

The recurrence dp[i] = 2 * dp[i-1] + dp[i-3] has a fixed lookback window of 3. This means you only ever need the last three computed values, just like Fibonacci only needs the last two. The space optimization follows the same template:

def numTilings(n):
    MOD = 10**9 + 7
    if n <= 2:
        return n

    a, b, c = 1, 1, 2
    for i in range(3, n + 1):
        a, b, c = b, c, (2 * c + a) % MOD

    return c

Any time you see a recurrence where dp[i] depends on dp[i-1], dp[i-2], ..., dp[i-k] for some constant k, you can apply this same trick: keep k variables and rotate them forward each iteration.

2. Telescoping recurrences

The full recurrence for this problem is dp[i] = dp[i-1] + dp[i-2] + 2 * sum(dp[0..i-3]). Writing the same equation for dp[i-1] and subtracting lets you cancel the summation term, collapsing it into dp[i] = 2 * dp[i-1] + dp[i-3]. Recognizing when a recurrence telescopes is a valuable skill. It turns an O(n^2) computation into O(n).

Edge cases to watch for

• n = 1: Only one vertical domino fits. Return 1.
• n = 2: Two vertical dominoes or two horizontal dominoes. Return 2.
• n = 3: Five valid tilings (3 domino-only, 2 with tromino pairs). Return 5.
• Large n: Values grow quickly. Apply mod 10^9 + 7 at every step to prevent overflow.
• Modular arithmetic: Make sure to apply the modulus inside the loop, not just at the end.

From understanding to recall

You have seen how the tromino creates a three-column dependency that transforms a Fibonacci-like recurrence into something slightly different. The algebra makes sense on paper. But can you re-derive the recurrence from scratch, without looking at the formula? Can you explain why the lookback is 3 and not 2? Can you write the space-optimized version from memory?

These are the kinds of questions spaced repetition helps you answer automatically. Instead of re-reading this post in three months and thinking "right, I forgot that part," you revisit the core pattern at increasing intervals until the reasoning is second nature. CodeBricks schedules those reviews for you, focusing on the building blocks that transfer across problems so you build real pattern recognition, not just problem-specific memory.

Related posts

• Climbing Stairs - Classic DP with similar recurrence structure
• Unique Paths - Grid-based DP counting paths
• Coin Change II - Another counting DP problem