Domino and Tromino Tiling

Problem in plain words

You have a board that is 2 cells tall and n cells wide. You may use two kinds of pieces as many times as you like: a 2x1 domino and an L-shaped tromino (three cells), and both may be rotated. Count the ways to cover the whole board with no gaps or overlaps, and return the count modulo 1_000_000_007.

For a 2x2 board there are 2 ways (two vertical dominoes, or two horizontal ones). Trominoes first appear at width 3, which has 5 tilings in total.

Intuition

Fill the board from left to right and look at the shape of the right edge. It is either flat (both rows end at the same column) or jagged (one row sticks out by one cell). A tromino is the only piece that can create or close a jagged edge. So track two counts:

• full[i]: ways to cover exactly the first i columns.
• part[i]: ways to cover the first i - 1 columns plus the top cell of column i only. By symmetry the bottom version has the same count.

Each count is built from smaller widths, exactly like the bottom-up Fibonacci DP lesson but with two interleaved sequences.

Approach

1. Recurrence for full: the last piece placed on a flat edge is either one vertical domino (full[i - 1]), two stacked horizontal dominoes (full[i - 2]), or a tromino that closes a jagged edge from width i - 1, which can be top or bottom (2 * part[i - 1]). So full[i] = full[i - 1] + full[i - 2] + 2 * part[i - 1].
2. Recurrence for part: a jagged edge at column i comes either from a tromino laid on a flat edge of width i - 2 (full[i - 2]), or from a horizontal domino extending the opposite jagged edge of width i - 1 (part[i - 1]). So part[i] = part[i - 1] + full[i - 2].
3. Base cases: full[0] = 1 (the empty board), full[1] = 1, part[0] = part[1] = 0.
4. Order: compute i = 2 to n, taking every sum modulo 10^9 + 7. Return full[n].

Dry run

Java solution

class Solution {
    public int numTilings(int n) {
        final long MOD = 1_000_000_007L;
        if (n <= 1) return 1;
        long[] full = new long[n + 1];
        long[] part = new long[n + 1];
        full[0] = 1;
        full[1] = 1;
        for (int i = 2; i <= n; i++) {
            full[i] = (full[i - 1] + full[i - 2] + 2 * part[i - 1]) % MOD;
            part[i] = (part[i - 1] + full[i - 2]) % MOD;
        }
        return (int) full[n];
    }
}

Python solution

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 10**9 + 7
        if n <= 1:
            return 1
        full = [0] * (n + 1)
        part = [0] * (n + 1)
        full[0] = full[1] = 1
        for i in range(2, n + 1):
            full[i] = (full[i - 1] + full[i - 2] + 2 * part[i - 1]) % MOD
            part[i] = (part[i - 1] + full[i - 2]) % MOD
        return full[n]

Complexity

Edge cases and common mistakes

• n = 1: only one vertical domino fits, so the answer is 1. Guard it before indexing full[2]-style arrays.
• Forgetting the factor 2: a jagged edge can stick out on top or on bottom; counting only one side gives 4 instead of 5 for n = 3.
• Overflow in Java: 2 * part[i - 1] on int values near the modulus overflows. Use long.
• Applying the modulus only at the end: intermediate values grow exponentially, so reduce at every step.