# [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)