点击获取AI摘要

790. 多米诺和托米诺平铺 M

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

lc-domino

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

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

示例 1:

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

示例 2:

输入: n = 1
输出: 1

提示：

1 <= n <= 1000

问题分析

我们要用两种瓷砖去完全铺满一个 $2 \times n$ 的长条面板：

多米诺骨牌（Domino）：尺寸 $2 \times 1$ ，可横放也可竖放。
托米诺骨牌（Tromino）的“L” 形：由三个小正方形组成一个“L”，可以旋转成 4 种方向。

求：对于给定的 $n$ ，共有多少种不同的铺法？由于数量可能非常大，最后对 $10^9+7$ 取模。

算法思路

$n=1$
只要竖放一个 $2\times1$ 的多米诺，方法数 = 1。
$n=2$
面板是 $2\times2$ ，可以：
1. 两个竖放的多米诺。
2. 两个横放的多米诺。
  方法数 = 2。
$n=3$
面板是 $2\times3$ ，枚举可得方法数 = 5。

令：

$dp[i]$ = 铺满 $2\times i$ 面板的方法数。

我们尝试根据最后一列（第 $i$ 列）怎么“收尾”来分类。

情况 A：最后竖着放一个多米诺

那么前 $i-1$ 列要完整铺好：共有 $dp[i-1]$ 种。

情况 B：最后两列都用横着的多米诺

第 $i-1$ 和第 $i$ 列各放一块横多米诺：前 $i-2$ 列完整铺好 ⇒ $dp[i-2]$ 种。

情况 C：托米诺 “L” 形

托米诺 “L” 会占用两列并且在第 $i$ 列上留出一个“半空”位置，所以它的影响要比前两种复杂。为此，我们引入辅助状态：

$f[i]$ = “前 $i$ 列铺到了半步”（即第 $i$ 列多出一个格子没被覆盖，呈现“⊔”或“⊓”形状）的方法数。

那么，可以得到两条递推：

$dp[i]$ 的推导
- A 情况贡献： $dp[i-1]$
- B 情况贡献： $dp[i-2]$
- C 情况：要用一个托米诺把从“半空”状态补齐过来。
  - 如果前一步是“半空” $f[i-1]$ （在第 $i-1$ 列空出一个格），那么可以放 2 种方向的托米诺把第 $i$ 列补满 ⇒ 贡献 $2\,f[i-1]$ 。
    所以：
    $dp[i]=dp[i−1]+dp[i−2]+2f[i−1].$
$f[i]$ 的推导
要在第 $i$ 列形成“半空”状态，有两种方式：
- 在完整的前 $i-2$ 列（ $dp[i-2]$ 种）末尾放一个托米诺，刚好留出一个半空。
- 在前一个也是半空 $f[i-1]$ 的基础上，放一个横多米诺扩展空位。
  所以：
$f[i] = dp[i-2] + f[i-1].$

我们可以把 $f$ 的式子代入 $dp$ 的式子，并做推导（略去具体代数），最终会得到一个只含 $dp$ 的简洁三项式：

$dp[i] = 2\,dp[i-1] + dp[i-3].$

初始化： $dp[0]=1,dp[1]=1,dp[2]=2.$ ，对于 $i<0$ 的 $dp[i]$ 视为 0（方便推导）。

这样，我们就只要维护前三个 $dp$ 值，就能一步步往后推。

时间复杂度

时间复杂度：每个 $i$ 只做常数次运算，总共 $O(n)$ 。

空间复杂度：只用到常数个变量， $O(1)$ 。

代码实现

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 10**9 + 7
        # 边界
        if n == 0:
            return 1
        if n == 1:
            return 1
        if n == 2:
            return 2
        
        # 初始化 dp[0], dp[1], dp[2]
        dp_i_3, dp_i_2, dp_i_1 = 1, 1, 2  # 分别对应 dp[0], dp[1], dp[2]
        
        # 从 i=3 推到 n
        for i in range(3, n+1):
            dp_i = (2 * dp_i_1 + dp_i_3) % MOD
            # 滚动窗口
            dp_i_3, dp_i_2, dp_i_1 = dp_i_2, dp_i_1, dp_i
        
        # 最终 dp[n] 存在 dp_i_1 中
        return dp_i_1

每轮计算出 dp_i = 2*dp[i-1] + dp[i-3]，然后向前滚动一格。