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.
- code
class Solution:
def numTilings(self, n: int) -> int:
if n == 1: return 1
C = 10 ** 9 + 7
f = [0] * (n+1)
p = [0] * (n+1)
f[1] = 1
f[2] = 2
p[2] = 1
for i in range(3, n+1):
f[i] = (f[i-2] + f[i-1] + 2 * p[i-1]) % C
p[i] = (p[i-1] + f[i-2]) % C
return f[n]
- code
class Solution:
def numTilings(self, n: int) -> int:
if n == 1: return 1
C = 10 ** 9 + 7
f_two_before = 1
f_cur = f_one_before = 2
p_one_before = 1
for i in range(3, n+1):
f_cur = (f_two_before + f_one_before + 2 * p_one_before) % C
p_cur = (p_one_before + f_two_before) % C
f_two_before = f_one_before
f_one_before = f_cur
p_one_before = p_cur
return f_cur
- code
class Solution:
def numTilings(self, n: int) -> int:
MOD = 1_000_000_007
if n <= 2:
return n
fPrevious = 1
fCurrent = 2
pCurrent = 1
for k in range(3, n + 1):
tmp = fCurrent
fCurrent = (fCurrent + fPrevious + 2 * pCurrent) % MOD
pCurrent = (pCurrent + fPrevious) % MOD
fPrevious = tmp
return fCurrent