790. Domino and Tromino Tiling

Problem¶

Count the tilings of a \(2 \times n\) board using rotatable dominoes and L-shaped trominoes. Return the count modulo \(10^9+7\).

n = 4 → 11 tilings

Key trick¶

A tromino can leave one square sticking out into the next column. Track that partial-board state, then eliminate it to get the recurrence \(f(n)=2f(n-1)+f(n-3)\).

Trap¶

Multiplying the number of tilings of smaller boards misses arrangements that cross the boundary between them. For \(n=4\), that approach gives \(10\) instead of \(11\).

Why is it interesting?¶

A seemingly complicated shape-based dynamic program reduces to three previous values.

Python solution¶

class Solution:
    def numTilings(self, n: int) -> int:
        if n <= 2:
            return n

        mod = 10**9 + 7
        prev3, prev2, prev1 = 1, 1, 2  # f(0), f(1), f(2)

        for _ in range(3, n + 1):
            # Eliminating the one-square-gap state gives this recurrence.
            cur = (2 * prev1 + prev3) % mod
            prev3, prev2, prev1 = prev2, prev1, cur

        return prev1

Time: \(O(n)\). Space: \(O(1)\).

Comment on my solution¶

Your base cases are correct, but the recurrence assumes tilings can be formed by combining independent width-three blocks. Tiles can cross those boundaries, so it misses valid tilings. The result also needs to be taken modulo \(10^9+7\).

# Ideas:
# - 1D DP
# - notice that:
#   - number of way to tile
#     - 1 * 2 -> 1
#     - 2 * 2 -> 2
#     - 2 * 3 -> 5
# - dp[i] = number of way to tile 2 * i
# - dp[i] = dp[i - 3] * 5 * 2 for i > 3

# Wrong Answer: 3/39 testcases passed
# 4
# Output: 10
# Expected: 11
class Solution:
    def numTilings(self, n: int) -> int:
        if n <= 2:
            return n
        if n == 3:
            return 5
        dp = [1] * (n + 1)
        dp[2] = 2
        dp[3] = 5
        for i in range(4, n + 1):
            dp[i] = dp[i - 3] * 5 * 2
        return dp[-1]
Solution().numTilings(3)
Solution().numTilings(4)

Extra¶

Complement to understand the recurrence¶

I don't get the recurrence. I can see the L shape sticking out into the next column. But there is two ways (L shapes) for this. The \(2f(n - 1)\) is the part I was doing, but I don't see the \(f(n - 3)\). What am I missing?

You’re right that the L-shaped protrusion has two orientations. What’s missing is that a protrusion leaves a partial board, not a completed smaller board, so it needs its own count.

Let:

• \(f(n)\) count fully tiled \(2 \times n\) boards.
• \(g(n)\) count boards tiled except for one specified square in the last column. The other choice of square has the same count by symmetry.

A full board can end with a vertical domino, two horizontal dominoes, or a tile that completes one of those partial boards:

The \(2\) accounts for the two mirrored protrusions. A partial board can either extend an earlier partial board or start its gap with a tromino:

Substituting that second equation into the first and simplifying gives:

The key point: \(2f(n-1)\) does not mean "choose one of two L shapes after tiling \(n-1\) columns." It is an algebraic result of eliminating the partial-board state. The \(f(n-3)\) term accounts for arrangements that this simplification would otherwise miss.

Show me this on an example for n = 4, I don't get what \(g(n)\) is counting and neither don't see how you get from \(f(n)=f(n-1)+f(n-2)+2g(n-1)\) to \(f(n)=2f(n-1)+f(n-3)\).

Think of \(g(3)\) as a nearly tiled \(2 \times 3\) board: exactly one square in column 3 is empty. Specify that the empty square is the top one. There are two ways:

AA.    AB.
ABB    ABB

Each letter is one tile; . is the empty square. Thus \(g(3)=2\). There are also two mirrored layouts with the bottom square empty.

For a \(2 \times 4\) board, an L tromino can cover that empty square and both squares of column 4. So the tilings that end this way number \(2g(3)=4\). The other endings give:

Now for the algebra. A partial board of width 3 comes either from extending a partial board of width 2 or from adding a tromino to a full board of width 1:

And the width-3 full-board equation tells us:

Substitute both into the equation for \(f(4)\):

The same substitution works for any \(n\), giving \(f(n)=2f(n-1)+f(n-3)\).