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