Medium

Domino and Tromino Tiling

LAB

Return the number of ways to tile a 2 by n board with dominoes and trominoes, modulo 1000000007.

EXAMPLES

Example 1

Input
{
  "n": 3
}

Output
5

FUNCTION SHAPE

n: int→int

SOLUTION NOTE

This requires tracking a "partial" state where one square sticks out. The recurrence is more complex - need dp(i) for complete rows and track prefix sums for tromino combinations.

Reveal reference solution +

pythonREFERENCE

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

    @cache
    def dp(i):
        if i <= 1: return 1
        if i == 2: return 2
        return (dp(i-1) + dp(i-2) + 2 * dp(i-3) +
                2 * sum(dp(j) for j in range(i-3))) % MOD

    return dp(n)

# Optimized with prefix sum
def numTilings(self, n: int) -> int:
    MOD = 10**9 + 7
    @cache
    def prefix(i):
        if i < 0: return 0
        return (prefix(i-1) + dp(i)) % MOD
    @cache
    def dp(i):
        if i < 0: return 0
        if i <= 1: return 1
        return (dp(i-1) + dp(i-2) + 2 * prefix(i-3)) % MOD
    return dp(n)

TimeO(n)

SpaceO(n)

Open on LeetCode ↗