题目

有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 “L” 的托米诺形。两种形状都可以旋转。

给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 + 7 取模 的值。

平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。

示例

示例 1:

输入: n = 3

输出: 5

解释: 五种不同的方法如上所示。

示例 2:

输入: n = 1

输出: 1

提示：

1 <= n <= 1000

思路

动态规划：

dp数组定义为dp[i][0]表示到达i-1块全部填满的可能情况，dp[i][0]表示到达i-1块缺一块的可能情况（这里缺的一块不分上下）。

状态转移方程为：

1.dp[i][0]=dp[i-1][0]+dp[i-2][0]+dp[i-1][1]

2.dp[i][1]=dp[i-2][0]*2+dp[i-1][1]

题解

class Solution:
    def numTilings(self, n: int) -> int:
    # n=1,2的情况直接返回
        if n==1:return 1
        if n==2:return 2
        dp=[[0]*2 for _ in range(n)]
        # 赋边界值
        dp[0]=[1,0]
        dp[1]=[2,2]
        for i in range(2,n):
            dp[i][0]=dp[i-1][0]+dp[i-2][0]+dp[i-1][1]
            dp[i][1]=dp[i-2][0]*2+dp[i-1][1]
        return dp[-1][0]%(10**9+7)