用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]