#790

Domino and Tromino Tiling

specialist · 880 · lc medium +31 · verified · 51.4% accepted · 4,144 likes · top 40%

Description

You have two tile shapes available: a 2 x 1 domino and an L-shaped tromino. Both may be rotated freely.

Given an integer n, determine the number of ways to completely tile a 2 x n board using these tiles. Because the count can be very large, return it modulo 10⁹ + 7.

Every square on the board must be covered. Two tilings are distinct when at least one pair of 4-directionally adjacent cells is covered by a tile in one arrangement but not the other.

Example 1:

Input: n = 3

Output: 5

Explanation: The five different ways are shown above.

Example 2:

Input: n = 1

Output: 1

Code

1

2

3

class Solution:
    def numTilings(self, n: int) -> int:

class Solution:
    def numTilings(self, n: int) -> int: