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

你這樣不如prefix sum用扣的

確實，不過還好題目給的範圍允許時間複雜度n^2

酷