[leetcode] 790. Domino and Tromino Tiling _ Algorithm Problem Solve for python

1. Problem

790. Domino and Tromino Tiling

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 109 + 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 show above.

Example 2:

Input: n = 1
Output: 1

Constraints:

• 1 <= n <= 1000

2. Solution

I solved this problem like this.

• Step
  • Using dynamic programming, i solved this problem.
  • dp[n][0] : nth cell / top is filled & bottom cell is empty
  • dp[n][1] : nth cell / bottom is filled & top cell is empty
  • dp[n][2] : nth cell / top & bottom is filled

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