Domino and Tromino Tiling

Problem

You have two tile shapes:

• a domino: a 2 × 1 (or 1 × 2) rectangle, and
• a tromino: an L-shaped tile covering three cells (a 2 × 2 square with one corner removed).

Both may be rotated. Count the number of ways to completely tile a 2 × n board with no gaps and no overlaps. The count grows quickly, so return it modulo 10^9 + 7.

Examples

• n = 1 → 1 — only a single vertical domino fits the 2 × 1 board.
• n = 3 → 5 — the five distinct tilings of a 2 × 3 board.
• n = 4 → 11.

Constraints

• 1 <= n <= 1000
• Answer is returned modulo 10^9 + 7.

With n up to 1000, an O(n) recurrence is sufficient. The difficulty is finding the recurrence, because trominoes leave partially filled columns.

Think about it first

TL;DR

Closed recurrence f(n) = 2·f(n-1) + f(n-3) (mod 10^9 + 7), computed with three rolling scalars — O(n) time, O(1) space.

The recurrence

Let f(n) be the number of tilings of a 2 × n board. The standard closed form is:

f(n) = 2 * f(n-1) + f(n-3)      for n >= 3
f(0) = 1,  f(1) = 1,  f(2) = 2

Reading the terms: 2·f(n-1) counts extending an (n-1)-tiling with a vertical domino, plus the mirror family of arrangements a tromino adds at the new column; f(n-3) counts the tilings that finish with a two-tromino block spanning three columns. Approach 4 derives this from first principles using two states.

Approach 1 — Brute-force recursion

Transcribe the recurrence with no caching.

def numTilings(n: int) -> int:
    MOD = 10 ** 9 + 7
    def f(k: int) -> int:
        if k == 0 or k == 1:
            return 1
        if k == 2:
            return 2
        return (2 * f(k - 1) + f(k - 3)) % MOD
    return f(n)

Complexity: exponential time (~O(2^n)), O(n) stack.

Each call spawns two more, and the tree recomputes the same f(k) values repeatedly. At n = 1000 this is far too slow.

Approach 2 — Top-down memoization

There are only n + 1 distinct values f(0) … f(n), so cache them.

from functools import cache

def numTilings(n: int) -> int:
    MOD = 10 ** 9 + 7
    @cache
    def f(k: int) -> int:
        if k == 0 or k == 1:
            return 1
        if k == 2:
            return 2
        return (2 * f(k - 1) + f(k - 3)) % MOD
    return f(n)

Complexity: O(n) time, O(n) space (cache + stack).

Approach 3 — Bottom-up tabulation

Compute from f(0) upward so each term’s three dependencies are already available.

def numTilings(n: int) -> int:
    MOD = 10 ** 9 + 7
    if n <= 2:
        return [1, 1, 2][n]
    dp = [0] * (n + 1)
    dp[0], dp[1], dp[2] = 1, 1, 2
    for k in range(3, n + 1):
        dp[k] = (2 * dp[k - 1] + dp[k - 3]) % MOD
    return dp[n]

Walkthrough (n = 4): seeds dp = [1, 1, 2, ?, ?]. dp[3] = 2·dp[2] + dp[0] = 2·2 + 1 = 5. dp[4] = 2·dp[3] + dp[1] = 2·5 + 1 = 11. Return 11.

Complexity: O(n) time, O(n) space.

Approach 4 — Two-state derivation, space-optimized

To derive the count instead of quoting it, track two ways a prefix of columns can end:

• full[i] = tilings of the first i columns with a flush (straight) right edge, and
• part[i] = tilings of the first i columns with exactly one cell of column i filled (a one-cell overhang).

Adding tiles at the right edge gives:

flowchart LR
    F2["full[i-2]"] --> F0["full[i]"]
    F1["full[i-1]"] --> F0
    P1["part[i-1]"] -->|"× 2 (tromino)"| F0
    F2 --> P0["part[i]"]
    P1 --> P0

full[i] = full[i-1] + full[i-2] + 2 * part[i-1]
part[i] = full[i-2] + part[i-1]
full[0] = 1, full[1] = 1
part[0] = 0, part[1] = 0

full[i-1] caps a flush edge with a vertical domino; full[i-2] caps it with two stacked horizontal dominoes; 2·part[i-1] closes a one-cell overhang with a tromino (two mirror orientations). An overhang at column i is created either by a tromino sitting on a flush edge two columns back (full[i-2]) or by extending an existing overhang with a horizontal domino (part[i-1]). Keeping only the last two values of each state gives O(1) space:

def numTilings(n: int) -> int:
    MOD = 10 ** 9 + 7
    if n == 1:
        return 1
    full2, full1 = 1, 1                       # full[i-2], full[i-1]
    part2, part1 = 0, 0                       # part[i-2], part[i-1]
    for _ in range(2, n + 1):
        full0 = (full1 + full2 + 2 * part1) % MOD
        part0 = (full2 + part1) % MOD
        full2, full1 = full1, full0
        part2, part1 = part1, part0
    return full1

Walkthrough (n = 3): start full = (full2, full1) = (1, 1), part = (0, 0).

• i=2: full0 = full1 + full2 + 2·part1 = 1 + 1 + 0 = 2; part0 = full2 + part1 = 1 + 0 = 1. Now full = (1, 2), part = (0, 1).
• i=3: full0 = 2 + 1 + 2·1 = 5; part0 = 1 + 1 = 2. Now full = (2, 5).

Return full1 = 5. (One more step, i=4: full0 = 5 + 2 + 2·2 = 11.)

Complexity: O(n) time, O(1) space. This two-state model produces exactly the same sequence as the closed form f(n) = 2·f(n-1) + f(n-3); use whichever you find easier to reproduce under pressure.

Common pitfalls

• Forgetting the modulus. f(1000) is enormous; reduce mod 10^9 + 7 at every step, not just at the end.
• Wrong base cases. f(0) = 1 (the empty board has one tiling) is what makes f(3) = 2·2 + 1 = 5 come out right; dropping it breaks the recurrence.
• Trusting a hand-rolled two-state model without checking small n. The overhang bookkeeping (which full/part index feeds which transition) is easy to get wrong, so verify against f(1..4) = 1, 2, 5, 11 first.
• Ignoring tromino rotations. Each L-tile has four orientations; the 2·part term accounts for the two that close an overhang at a given edge.

Pattern takeaway

Tiling counts are 1-D DP where the recurrence isn’t obvious from the problem statement. Two routes work: discover a closed linear recurrence by computing small cases (1, 2, 5, 11, 24, … → f(n) = 2f(n-1) + f(n-3)), or introduce auxiliary states (full/partial) to keep each transition local. The general lesson: when tiles leave partially filled boundaries, add one state per boundary shape, and validate a guessed recurrence against a handful of brute-forced small answers before trusting it.