多米诺和托米诺平铺

Problem

You have two types of tiles: a \(2 \times 1\) domino shape and a tromino shape. You may rotate these shapes.

Given an integer \(n\), return the number of ways to tile a \(2 \times n\) board. Since the answer may be very large, return it modulo \(10^9 + 7\).

In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.

Example 1:

Input: n = 3

Output: 5

Explanation: The five different ways are shown above.

Example 2:

Input: n = 1

Output: 1

Constraints:

• 1 <= \(n\) <= 1000

Idea

Tile the board column by column with dynamic programming, using two states:

• \(f[i]\): the number of ways to fully tile the first \(i\) columns.
• \(p[i]\): the number of ways to tile the first \(i - 1\) columns plus only the top square of column \(i\). The case with only the bottom square is symmetric, so it has the same count.

Look at the tiles that finish the last column:

• \(f[i] = f[i-1] + f[i-2] + 2 \cdot p[i-1]\): one vertical domino, two horizontal dominoes, or a tromino that fills a half-tiled column \(i - 1\) (top or bottom, hence the factor 2).
• \(p[i] = p[i-1] + f[i-2]\): a horizontal domino on the top row after a half-tiled column \(i - 1\), or a tromino that covers column \(i - 1\) and the top square of column \(i\).

Start with \(f[0] = f[1] = 1\) and \(p[0] = p[1] = 0\), take every value modulo \(10^9 + 7\), and return \(f[n]\).

Time complexity: \(O(n)\), Space complexity: \(O(n)\), which can be reduced to \(O(1)\) since each step only looks back two columns

Pseudo Code

def num_tilings(n):
    MOD = 10**9 + 7
    f = [0] * (n + 1)  # f[i]: i full columns
    p = [0] * (n + 1)  # p[i]: i - 1 full columns + top of column i
    f[0] = f[1] = 1

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

    return f[n]