790. Domino and Tromino Tiling

Problem Statement

link: LeetCode.cn LeetCode You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes. Given an integer n, return the number of ways to tile an 2 x 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:

Input: n = 3 Output: 5

Input: n = 1 Output: 1

Solution Approach

Use dynamic programming to maintain states for partially and fully covered sections of the board, updating the states based on possible tile placements to calculate the total number of ways to tile a 2 x n board.

Algorithm

1. Define DP States: Use a 2D DP array where dp[i][j] represents the number of ways to cover the board up to column i with different states of coverage (0 to 3) for the last two columns.
2. State Transitions: Develop transition formulas based on placing dominos and trominos, updating the DP states accordingly to reflect new configurations.
3. Final Calculation: Sum up the ways to fully cover the board (dp[n][3]), using modulo 10**9+7 to handle large numbers, to get the total number of tiling ways for a 2 x n board.

Implement

    class Solution: def numTilings(self, n: int) -> int:
    mod = 10 ** 9 + 7
    dp = [[0] * 4 for _ in range(n + 1)]
    dp[0][3] = 1
    for i in range(1, n + 1):
        dp[i][0] = dp[i - 1][3]
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % mod
        dp[i][3] = (((dp[i - 1][0] + dp[i - 1][1]) % mod + dp[i - 1][2] )% mod + dp[i - 1][3]) % mod
    return dp[n][3]

    
    

Twitter  facebook  Email