LeetCode 解題紀錄 790. Domino and Tromino Tiling
Oct 20, 2022
題目
給定兩種骨牌分別是一字型(2格)與 L 型 (3格)，求填滿一個 2 x n 的長條形所有可能的排法
限制
- 1≤ n ≤ 1000
觀察
- 因為每一格都必須填滿，所以只有幾種固定的 pattern
- 每增加一行，就會出現新的排列方式
- 可以放一個直的1x2，排列方式就是上一個的總和
- 倒退一格可以放兩個橫的1x2，排列方式是上兩個的總和
- 倒退兩格可以放兩個 L 型，可以交換所以是上三個的總和乘 2
- 依此類推到最後一個都可以得到新的排列
思路
- 這是典型的 DP 問題，基於之前的計算結果取得新的結果
- base case 是一行的時候，只有一種排列
Trial 1
結果
時間複雜度為 O(n²)，空間複雜度為 O(n)，排名落後，有精進的空間
Trial 2
- 使用 prefix sum 累加之前的結果，節省第二個 for loop
結果
時間複雜度降為 O(n)，空間複雜度為 O(2n) = O(n)，執行速度加快了，但還不夠好，研究最佳解的作法
Trial 3
- 最佳解的作法是進一步推導更精簡的公式，原本的 DP 計算式是
dp[i] = dp[i-1]+dp[i-2]+2*(dp[i-3]+dp[i-4]+…+dp[0])把 dp[i-3] 拿出來變成
dp[i] = dp[i-1]+dp[i-2]+dp[i-3]+dp[i-3]+2*(dp[i-4]+dp[i-5]+…+dp[0])而 dp[i-1] 的計算式是
dp[i-2]+dp[i-3]+2*(dp[i-4]+dp[i-5]+…+dp[0])所以 DP 計算式就變成了，減少了迴圈計算的部份
dp[i] = 2*dp[i-1]+dp[i-3]
結果
時間空間複雜度不變，執行時間與記憶使用進一步減少。DP bottom up 的程式碼常常看起來出奇的簡單，但推導過程就沒有那麼直覺了，非常需要多做題目來增加經驗
