Re: [閒聊] 每日leetcode

看板Marginalman作者pandix (麵包屌)時間7月前 (2025/05/06 00:59)推噓2(2推 0噓 2→)

※ 引述《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 -- 蛤? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.228.8.244 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1746464374.A.750.html

推

uiojkl789

05/06 01:02, 7月前 , 1^F

05/06 01:02, 1^F

真的沒有很帥我很能客觀評價自己

推

sixB

05/06 01:02, 7月前 , 2^F

05/06 01:02, 2^F

→

sixB

05/06 01:02, 7月前 , 3^F