题目

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

XX <- 多米诺

XX <- "L" 托米诺
X
给定 N 的值，有多少种方法可以平铺 2 x N 的面板？返回值 mod 10^9 + 7。

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

示例:
输入: 3
输出: 5
解释:
下面列出了五种不同的方法，不同字母代表不同瓷砖：
XYZ XXZ XYY XXY XYY
XYZ YYZ XZZ XYY XXY
提示：

N 的范围是 [1, 1000]

解答

我们使用动态规划来解决这个问题。首先理解一下题意，给出了两种不同形状的砖块，一种是I形（2个单位面积），另一种是L形状（三个单位面积），要求中这些瓷砖铺设2×N的区域，为了便于表示，我们看做要铺设成两行N列的区域。例如：
XXX
XXX
这里的N就是3。

我们从左到右逐列遍历，设当前遍历到第i列，这一列一共有四个可能状态，记为0,1,2,3，设“O”代表该位置没有填充瓷砖，“X”代表该位置填充瓷砖：
0 1 2 3
O X O X
O O X X

第i列的四种状态都可以从第i-1列的状态获得，
状态0的获取方式有两种，如果第i-1列是状态0，那么可以加入I形瓷砖获得；如果第i-1列是状态1，那么可以通过不加入任何瓷砖获得。
状态1的获取方式有两种，如果第i-1列是状态0，那么可以加入L形瓷砖获得；如果第i-1列是状态2，那么可以加入一个横着摆放的I形瓷砖获得。
状态2的获取方式有两种，如果第i-1列是状态0，那么可以加入颠倒的L形瓷砖获得；如果第i-1列是状态1，那么可以加入一个横着摆放的I形瓷砖获得。
状态3的获取方式有三种，如果第i-1列是状态0，那么可以加入两个横着摆放的I形瓷砖获得；如果第i-1列的状态是1，那么可以加入一个L形瓷砖获得；如果第i-1列是状态2，那么可以加入一个颠倒的L形瓷砖获得。

定义包含四个元素的数组dp，分别表示获得以上四个状态的可能排列数，初始状态为[1,0,0,0]，则根据以上推导写出递推关系式：
dp_new[0] = dp[0] + dp[3]
dp_new [1] = dp[0] + dp[2]
dp_new [2] = dp[0] + dp[1]
dp_new [3] = dp[0] + dp[1] + dp[2]
dp = dp_new

最后返回dp[0]的结果即可。

class Solution(object):
    def numTilings(self, N):
        dp = [1, 0, 0, 0]
        for _ in range(N):
            dp = [dp[0] + dp[3], dp[0] + dp[2], dp[0] + dp[1], dp[0] + dp[1] + dp[2]]
        return dp[0] % (10 ** 9 + 7)

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析