Domino and Tromino Tiling

main.md

Question

Approach

I used dynamic programming to build a solution bottom-up. I defined dp[i] as the number of ways to tile a 2×i board. The recurrence relation came from understanding that I can add a vertical domino (dp[i-1]), a pair of horizontal dominoes or trominoes (dp[i-2]), and more complex tromino arrangements that require tracking prior gaps using a separate variable (dp[i-3] and beyond). I initialized the base cases for n = 1, 2, 3, and iteratively built up the solution to n. To avoid overflow, I applied modulo 10^9 + 7 at every step.

Implementation

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

        if n == 1:
            return 1
        if n == 2:
            return 2
        if n == 3:
            return 5
        
        dp = [0] * (n + 1)
        dp[1], dp[2], dp[3] = 1, 2, 5
        
        for i in range(4, n + 1):
            dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD
            
        return dp[n]

Complexities

• Time: O(n)
• Space: O(n)