※ 引述《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

你為什麼這麼帥又這麼卷

這題這麼經典ㄛ你的寫法好厲害==我好崇拜你

別卷了