楼主:
pandix (面包屌)
2025-05-06 00:59:31※ 引述《yam276 (史莱哲林的优等生)》之铭言：
: 790. Domino and Tromino Tiling
: https://leetcode.com/problems/domino-and-tromino-tiling/
: 题意：
: 你有2x1跟L型的多米诺
: 能拼出几种2xn的矩阵
这题也写好多次了
在填第i行的时候可以参考i-1行的状态
有四种状态 a.上面一格 b.下面一格 c.两格都有 d.都是空的
第i行要 a 的话 i-1行可以是 b (插直的) 或 d (插L)
i-2行
|i-1行
||i行
|||
O OXX O OXX
OO -> OO O -> OX
第i行要 b 的话
OO OO O OX
O -> OXX O -> OXX
第i行要 c 的话
OO OOX O OXX OO OOX O OXX
O -> OXX OO -> OOX OO -> OOX O -> OYY
后面两种很容易重复计算 要小心
第i行要 d 的话
OO OO
OO -> OO
就是 i-1 的 c
O OX
O -> OX
不用加上这种状况的原因是他已经被包含在 i-1 的 c 里面了
最后考虑一下起始状态就好
填第一行的时候左边等于是墙壁 也就是两格都有的状态 塞不进L
class Solution:
def numTilings(self, n: int) -> int:
up, bot, both, empty = 0, 0, 1, 0
mod = 10**9+7
for i in range(n):
up, bot, both, empty = bot+empty, up+empty, empty+up+bot+both,
both
return both % mod