用L型和I型兩種方塊填充2*N的格子，問一共幾種填充方式，DP
參考了Discussion的思路->https://leetcode.com/problems/domino-and-tromino-tiling/solutions/116506/python-recursive-dp-solution-with-cache-w-explanation/
dp[i][0]代表用掉了2*i個格子，一共多少種填充方式
狀態可以來自于dp[i - 1][0]再放上一個2*1的I形格子+dp[i - 2][0]再橫著放兩個2*1的I形格子+dp[i - 1][1]再放上兩個L形格子，根據dp[i - 1][1]的形狀不同（上面多出一個或者下面多出一個）有兩種
dp[i][1]代表用掉了2*(i-1)+1個格子，一共多少種填充方式
狀態可以來自于dp[i - 1][0]再放上一個L形格子+dp[i - 1][1]再橫著放一個2*1的I形格子
dp[i][0] = dp[i - 1][0] + dp[i - 2][0] + 2 * dp[i - 1][1]
dp[i][1] = dp[i - 2][0] + dp[i - 1][1]
1 #790
2 #Runtime: 19 ms (Beats 94%)
3 #Memory: 13.5 MB (Beats 54%)
4
5 class Solution(object):
6 def numTilings(self, n):
7 """
8 :type n: int
9 :rtype: int
10 """
11 if n < 3:
12 return n
13 M = 10**9 + 7
14 dp = [[0, 0] for _ in range(n + 1)]
15 dp[1][0] = 1
16 dp[2][0] = 2
17 dp[2][1] = 1
18 for i in range(3, n + 1):
19 dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + 2 * dp[i - 1][1]) % M
20 dp[i][1] = (dp[i - 2][0] + dp[i - 1][1]) % M
21 return dp[n][0]