題目敘述

題目難度: medium
題目敘述: 題目給定兩種骨牌，一種會是 2*1 大小的長方形骨牌，另一種會是 L型骨牌。給定整數 n，請回傳用這兩種骨牌撲滿 2*n 大小板子的擺放方式。答案可能會很大，因此回傳時要對 1000000007 取餘數

解法

我的解法

這題好像也是經典的 dp題目，首先要定義我們要解的 dp[n] 代表的意義，既然我們最後要回傳的是有幾種擺放方式，那 dp 內要存放的就是有幾種擺放方法。

因此對於 dp[n] 代表 2*n 大小的板子可以被兩種骨牌撲滿的方法數

class Solution {
public:
    
    int numTilings(int n) {
        
        if(n==1) return 1;
        if(n==2) return 2;

        // dp[n]: the number of methods of fill 2*n board using domino and trimino tiles
        vector<long long> dp(n+1);
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;

        for(int i=3; i<=n; i++){
            dp[i] = ( 2* dp[i-1]+ dp[i-3]) % (1000000007);
        }
        return (int)dp[n];
    }
};

所以如果 n=1 代表板子大小 2*1 的骨牌擺放數，只會有一種。如果 n=2 則代表對於 2*2 的板子有多少擺放數量，都只能用 2*1 骨牌放，只會是兩種，這些會是 base case。

所以到了 2*n 的板子，我們想像一下板子的最右邊可以怎麼擺:

情況 A：最後一列用一塊直的骨牌佔掉 → 左邊變板子大小為 2*n-1 的子問題 → dp[n-1]
情況 B：最後兩列完全用骨牌鋪：兩個橫的多米諾 → 左邊變成2*n-2 的子問題 → dp[n-2]
情況 C：最後三列中出現 L 形 tromino 的組合 → 左邊變成2*n-3 的子問題 → dp[n-3]

其實如果寫成算式，還可以再化簡， dp[n-2] 的狀況，可以拆成

讓所有跟 dp[n-2] 有關的情況，全都被重新歸類到 2*dp[n-1] 和 dp[n-3] 這兩種型態裡面，但為甚麼要這樣? 這會跟最後的放法有關係

我們把 2×n 棋盤最右邊這一小段拿出來看：

類型 A：最後一欄是「完整填好的」

也就是第 n 欄沒有凸出去、沒有缺角，長這樣（只看最後一欄）：

1
2

[]
[]

只要「最後一欄是完整的」，那左邊一定是一個完整的 2×(n−1) 為何會是 2×(n−1) ? 因為讓右邊這一欄變成完整的有兩種方式

這兩種方式 + 左邊任意鋪法：

直放一個直的 2×1 骨牌
或者是 來自更複雜的組合 ，例如之前有一些 L 形骨牌跨過來，最後收尾收成一個完整直欄

因此，所有「最後一欄完整」的情況，加起來總數 = 2 * dp[n-1]

類型 B：最後一欄「不是獨立的」，而是被 L 形骨牌黏住

右邊三欄長得有點像樓梯、缺角，需要至少三欄才容得下完整的 L 形組合。大致可以想成，會有一個 L 骨牌跨到第 n 欄，然後另外還有對稱的 L 配合填滿，因此最右邊三欄合起來被一組（或幾組）L 骨牌消耗掉

所以這一類型的總數 = dp[n-3] (會剩下 2 * n-3 大小的板子作為子問題)

所以我們把兩種類型加起來：

1
2
3

dp[n] = （最後一欄完整） + （最後三欄是一坨 L 結尾）
      = 2 * dp[n-1]         +      dp[n-3]

會得到遞迴式:

1	dp[n] = 2 * dp[n-1] + dp[n-3];

執行結果

複雜度

時間複雜度: $O(N)$

空間複雜度: $O(N)$