作者:
leafff (LEAF)
2025-05-06 00:19:10※ 引述《yam276 (史萊哲林的優等生)》之銘言:
: 790. Domino and Tromino Tiling
: https://leetcode.com/problems/domino-and-tromino-tiling/
: 題意:
: 你有2x1跟L型的多米諾
: 能拚出幾種2xn的矩陣
我想到的解法是只用一維的dp,
具體思路是把每一次dp得到的數字都設為此時有幾種2*i的骨牌組合,
並設2*0為1種,
不過時間複雜度就會高一點
例如2*1矩形有1種組合,
2*2矩形可以是2*1矩形再加上1個豎直擺放的長方形骨牌,
或從頭開始擺2個橫向擺放的長方形骨牌,
結果是1+1=2種
2*3矩形則是除2*2矩形加1個直骨牌與2*1矩形加2個橫骨牌之外,
還可以從頭開始擺2個L形骨牌,有2種擺法
結果是2+2+1=5種
歸納結果,
如果當前要組2*i的矩形,
在i>2的情況下,
其組合總數是dp[0:i-2] * 2 + dp[i-2] + dp[i-1]種