title
We have two types of tiles: a 2x1 domino shape, and an “L” tromino shape. These shapes may be rotated.
XX <- domino
XX <- "L" tromino
X
Given N, how many ways are there to tile a 2 x N board? Return your answer modulo 10^9 + 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:
Input: 3
Output: 5
Explanation:
The five different ways are listed below, different letters indicates different tiles:
XYZ XXZ XYY XXY XYY
XYZ YYZ XZZ XYY XXY
Note:
- N will be in range
[1, 1000].
solution
class Solution:
def numTilings(self, N: int) -> int:
# 1, 2, 3 = top, down, top&down
memo = {}
p = 10 ** 9 + 7
def f(i, t):
if (i, t) in memo:
return memo[(i, t)]
# corner case:
if i <= 0:
if i == 0 and t == 3:
return 1
else:
return 0
if t == 1:
r = f(i - 2, 3)%p + f(i - 1, 2)%p
elif t == 2:
r = f(i - 2, 3)%p + f(i - 1, 1)%p
else:
r = f(i - 1, 3)%p + f(i - 1, 1)%p + f(i - 1, 2)%p + f(i - 2, 3)%p
r = r % p
memo[(i, t)] = r
return r
#
# assert f(1, 3) == 1
# assert f(1, 1) == f(1, 2) == 0
# assert f(2, 1) == f(2, 2) == 1
# assert f(2, 3) == 2
return f(N, 3)