LeetCode 790: Domino and Tromino Tiling

Problem Restatement

We are given an integer n.

We need to count how many ways there are to tile a 2 x n board using two tile types:

Both tile types may be rotated.

Return the number of tilings modulo:

10**9 + 7

Every square must be covered exactly once. Two tilings are different if their tile placements differ.

Input and Output

Function shape:

class Solution:
    def numTilings(self, n: int) -> int:
        ...

Examples

Example 1:

n = 3

There are 5 ways to tile a 2 x 3 board.

So the answer is:

5

Example 2:

n = 1

Only one vertical domino can cover a 2 x 1 board.

So the answer is:

1

First Thought: Build Boards Recursively

A direct idea is to place a tile in the leftmost uncovered cell and recursively fill the rest.

This works for small n, but it creates many repeated subproblems.

For example, many different early placements can leave the same remaining board shape. We should store the number of ways for each board width and state.

Key Insight

When tiling from left to right, the board can be in two important states.

The missing corner may be the top or bottom cell. These two cases are symmetric, so one variable is enough.

Now derive the transitions.

To fully tile width i:

1. Add one vertical domino to a full 2 x (i - 1) board.
2. Add two horizontal dominoes to a full 2 x (i - 2) board.
3. Add one tromino to one of two partial states of width i - 1.

So:

full[i] = full[i - 1] + full[i - 2] + 2 * partial[i - 1]

To create a partial state of width i:

1. Extend a full 2 x (i - 2) board with one tromino.
2. Extend a partial 2 x (i - 1) board with one horizontal domino.

So:

partial[i] = full[i - 2] + partial[i - 1]

Algorithm

Use dynamic programming.

Base cases:

full[0] = 1
full[1] = 1
partial[0] = 0
partial[1] = 0

Then for i from 2 to n:

full[i] = full[i - 1] + full[i - 2] + 2 * partial[i - 1]
partial[i] = partial[i - 1] + full[i - 2]

Return:

full[n]

Correctness

We prove that full[i] stores the number of ways to fully tile a 2 x i board, and partial[i] stores the number of ways to tile a 2 x i board with exactly one missing corner cell.

The base cases are correct. An empty board has one complete tiling, so full[0] = 1. A 2 x 1 board has exactly one complete tiling, using one vertical domino, so full[1] = 1. A partial board of width 0 or 1 cannot be formed in the needed way, so the partial values start at 0.

For full[i], consider the right end of a complete tiling. If the last column is covered by a vertical domino, the remaining board is a full 2 x (i - 1) board. If the last two columns are covered by two horizontal dominoes, the remaining board is a full 2 x (i - 2) board. Otherwise, the final completion must use a tromino to fill a previous partial state. There are two symmetric partial states, top-missing and bottom-missing, so this contributes 2 * partial[i - 1].

For partial[i], the missing corner can be formed either from a full 2 x (i - 2) board by placing one tromino, or from a smaller partial state by extending it with one horizontal domino. These two cases are disjoint and cover all ways to create such a partial boundary.

Thus the transitions count every valid tiling exactly once. Therefore, full[n] is the number of complete tilings of the 2 x n board.

Complexity

The space can be reduced to O(1) because each step uses only the previous two full values and the previous partial value.

Implementation

class Solution:
    def numTilings(self, n: int) -> int:
        mod = 10**9 + 7

        if n == 1:
            return 1

        full = [0] * (n + 1)
        partial = [0] * (n + 1)

        full[0] = 1
        full[1] = 1

        for i in range(2, n + 1):
            full[i] = (
                full[i - 1]
                + full[i - 2]
                + 2 * partial[i - 1]
            ) % mod

            partial[i] = (
                partial[i - 1]
                + full[i - 2]
            ) % mod

        return full[n]

Code Explanation

We use the required modulo:

mod = 10**9 + 7

The complete tiling array is:

full = [0] * (n + 1)

The partial tiling array is:

partial = [0] * (n + 1)

The base cases are:

full[0] = 1
full[1] = 1

Then we compute every board width from left to right:

for i in range(2, n + 1):

The complete state transition is:

full[i] = (
    full[i - 1]
    + full[i - 2]
    + 2 * partial[i - 1]
) % mod

The partial state transition is:

partial[i] = (
    partial[i - 1]
    + full[i - 2]
) % mod

Finally, the answer is the number of complete tilings:

return full[n]

Space-Optimized Version

There is also a one-state recurrence:

dp[i] = 2 * dp[i - 1] + dp[i - 3]

with:

dp[1] = 1
dp[2] = 2
dp[3] = 5

Implementation:

class Solution:
    def numTilings(self, n: int) -> int:
        mod = 10**9 + 7

        if n <= 2:
            return n

        a = 1
        b = 2
        c = 5

        if n == 3:
            return c

        for _ in range(4, n + 1):
            a, b, c = b, c, (2 * c + a) % mod

        return c

Testing

def run_tests():
    s = Solution()

    assert s.numTilings(1) == 1
    assert s.numTilings(2) == 2
    assert s.numTilings(3) == 5
    assert s.numTilings(4) == 11
    assert s.numTilings(5) == 24

    print("all tests passed")

run_tests()

Test coverage: