M790.多米诺和拖米诺平铺

dp, https://leetcode.cn/problems/domino-and-tromino-tiling/

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

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

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

示例 1:

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

示例 2:

输入: n = 1
输出: 1

提示：

1 <= n <= 1000

解题思路

我们定义一个数组 dp[i] 表示用多米诺和托米诺覆盖 2 x i 的面板的总方法数。

另外还引入一个辅助数组 dp2[i] 表示覆盖 2 x i 的面板并“突出”一个单位方块（一个“悬挂”的块）的方法数。这个状态是处理托米诺造成的不对称结构的关键。

✅ 状态转移公式

dp[0] = 1        # 空板子有1种放法
dp[1] = 1        # 只放1个竖着的多米诺
dp[2] = 2        # 横着放两个多米诺 或 两个竖着的

从n = 3 开始：
dp[n] = dp[n - 1] + dp[n - 2] + 2 * dp2[n - 1]
dp2[n] = dp2[n - 1] + dp[n - 2]

解释：

dp[n - 1]：最后放一个竖的多米诺
dp[n - 2]：最后放两个横的多米诺
2 * dp2[n - 1]：最后放一个托米诺（左上或右上 L 形）

✅ Python 实现

python

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 10**9 + 7
        
        if n == 1:
            return 1
        dp = [0] * (n + 1)
        dp2 = [0] * (n + 1)
        dp[0], dp[1], dp[2] = 1, 1, 2
        dp2[0], dp2[1], dp2[2] = 0, 0, 1
    
        for i in range(3, n + 1):
            dp[i] = (dp[i - 1] + dp[i - 2] + 2 * dp2[i - 1]) % MOD
            dp2[i] = (dp2[i - 1] + dp[i - 2]) % MOD
    
        return dp[n]

✅ dp[n-2] 只对应横着放两个砖的唯一方法。

❌ 不该加 2 * dp[n-2]，因为“两个竖着的砖”不构成新的方式，它们已包含在 dp[n-1] 和更早的状态中。

✅ 1. 主状态 dp[n] 表示什么？

dp[n] 是将一个 2 x n 的面板完全铺满的方法总数。

我们想办法把 2 x n 的面板分解为 已知长度 的面板 + 一些最后一步的摆放方式。

dp[n] = dp[n - 1] + dp[n - 2] + 2 * dp2[n - 1]

含义解释：

dp[n - 1]：最后放一个竖着的多米诺
- 例子：在 2 x (n - 1) 处先铺好，然后竖着放一个多米诺。
dp[n - 2]：最后放两个横着的多米诺
- 横着摆两个 1 x 2，刚好填满最后两列。
2 * dp2[n - 1]：最后放一个托米诺（L 形）
- dp2[n - 1] 表示在 2 x (n - 1) 的板子里，有一块“缺口”（就是 L 形托米诺能挂上的那种不对称结构）。
- 因为托米诺有两种形状（左下角缺、右下角缺），所以乘以 2。

✅ 2. 辅助状态 dp2[n] 表示什么？

dp2[n] 表示铺到 2 x n 的时候，有一个悬挂的格子（“凸出”一个小块）的方法数。

转移式：

dp2[n] = dp2[n - 1] + dp[n - 2]

含义解释：

dp2[n - 1]：在前一步就已经“凸出来”，这一步不做任何操作，继续保留这个凸出
dp[n - 2]：在 2 x (n - 2) 已完全铺好的板子上，放一个托米诺造成的凸出结构
- 比如放一个 L 形，覆盖第 n-1 和 n 两列的三个格子，剩下一个凸出来

M790.多米诺和拖米诺平铺 ​

M790.多米诺和拖米诺平铺