---

0790. 多米诺和托米诺平铺

• 标签：动态规划
• 难度：中等

题目链接

• 0790. 多米诺和托米诺平铺 - 力扣

题目大意

描述：

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

给定整数 $n$。

要求：

返回可以平铺 $2 \times n$ 的面板的方法的数量。返回对 $10^9 + 7$ 取模的值。

说明：

• 平铺：指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。
• $1 \le n \le 10^{3}$。

示例：

• 示例 1：

示例 1:
输入: n = 3
输出: 5
解释: 五种不同的方法如上所示。

• 示例 2：

输入: n = 1
输出: 1

解题思路

思路 1：动态规划

这道题需要计算平铺 $2 \times n$ 面板的方法数。

状态定义：

• 定义 $dp[i][0]$ 表示平铺到第 $i$ 列，且第 $i$ 列两行都被填满的方法数。
• 定义 $dp[i][1]$ 表示平铺到第 $i$ 列，且第 $i$ 列只有上行被填满的方法数。
• 定义 $dp[i][2]$ 表示平铺到第 $i$ 列，且第 $i$ 列只有下行被填满的方法数。

状态转移：

• $dp[i][0]$ 可以从以下状态转移：
  • $dp[i-1][0]$：放置一个竖直的多米诺。
  • $dp[i-2][0]$：放置两个水平的多米诺。
  • $dp[i-1][1]$ 和 $dp[i-1][2]$：放置托米诺。
• $dp[i][1]$ 可以从 $dp[i-1][0]$ 或 $dp[i-1][2]$ 转移。
• $dp[i][2]$ 可以从 $dp[i-1][0]$ 或 $dp[i-1][1]$ 转移。

递推公式：

• $dp[i][0] = (dp[i-1][0] + dp[i-2][0] + dp[i-1][1] + dp[i-1][2]) \mod (10^9 + 7)$
• $dp[i][1] = (dp[i-1][0] + dp[i-1][2]) \mod (10^9 + 7)$
• $dp[i][2] = (dp[i-1][0] + dp[i-1][1]) \mod (10^9 + 7)$

思路 1：代码

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 10**9 + 7
        
        if n == 1:
            return 1
        if n == 2:
            return 2
        
        # dp[i][0]: 第 i 列两行都填满
        # dp[i][1]: 第 i 列只有上行填满
        # dp[i][2]: 第 i 列只有下行填满
        dp = [[0] * 3 for _ in range(n + 1)]
        dp[0][0] = 1
        dp[1][0] = 1
        
        for i in range(2, n + 1):
            dp[i][0] = (dp[i-1][0] + dp[i-2][0] + dp[i-1][1] + dp[i-1][2]) % MOD
            dp[i][1] = (dp[i-2][0] + dp[i-1][2]) % MOD
            dp[i][2] = (dp[i-2][0] + dp[i-1][1]) % MOD
        
        return dp[n][0]

思路 1：复杂度分析

• 时间复杂度：$O(n)$。需要遍历 $n$ 列。
• 空间复杂度：$O(n)$。可以优化到 $O(1)$，只保留最近的几个状态。