Re: [閒聊] 每日LeetCode
790. Domino and Tromino Tiling
你有兩種骨牌，一種是兩個方塊的I型，一種是三個方塊的L型
https://assets.leetcode.com/uploads/2021/07/15/lc-domino.jpg
請你算出用這兩種骨牌組成 2*n 的盤面總共有幾種擺列方法
Example 1:
Input: n = 3
Output: 5
直接上圖: https://assets.leetcode.com/uploads/2021/07/15/lc-domino1.jpg
Example 2:
Input: n = 1
Output: 1
思路:
1.如果只有I型的骨牌就很好解了，dp[n] = dp[n-1] + dp[n-2]
也就是 n-1 的狀況補一塊直的，加上 n-2 的狀況補兩塊橫的
n-2 補兩塊直的不用考慮，已經算在 n-1裡了
2.加上L型就稍微有點麻煩，不能直接用 dp[n-3] 補兩塊L型
因為也有可能是頭尾L型中間夾很多上下平躺的I，也就是說L型不一定會連續出現
這裡為了要考慮插入L型的狀況，可以用狀態轉移去解決
考慮四種第 n 行的狀態，分別是上面/下面有方塊，上下都有，上下都沒有
那麼在排 dp[n] 的時候就可以由 dp[n-1] 的結果得來
dp[n][上面有] = dp[n-1][下面有] 上排插一個I + dp[n-1][都沒有] 插一個L
dp[n][下面有] = dp[n-1][上面有] 下排插一個I + dp[n-1][都沒有] 插一個L
dp[n][都沒有] = dp[n-1][都有]
dp[n][都有] = dp[n-1][下面有] 插L + dp[n-1][上面有] 插L + dp[n-1][都有] 插I
+ dp[n-1][都沒有] 插兩個橫的I，補直的不用考慮
最後直接設定 n=1 時 dp[1][都沒有] = dp[1][都有] = 1 就好
Python code:
class Solution:
def numTilings(self, n: int) -> int:
up, down, both, emp = 0,0,1,1
for i in range(n-1):
up, down, both, emp = emp+down, emp+up, both+emp+up+down, both
return both % (10**9+7)
應該是要邊做邊取模的 不過我懶
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.193.79 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1671860802.A.079.html
推
12/24 14:43,
3年前
, 1F
12/24 14:43, 1F
→
12/24 19:35,
3年前
, 2F
12/24 19:35, 2F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 150 之 719 篇)：