Domino and Tromino Tiling

題目描述

用 Domino（2×1）和 Tromino（L 形）鋪滿 2×n 的棋盤，回傳方法數（mod 10^9+7）。

輸入：n = 3
輸出：5

輸入：n = 1
輸出：1

解題思路

觀察規律

手動列舉小 case：n=1→1, n=2→2, n=3→5, n=4→11。嘗試找出遞推關係

定義狀態

f(n) = 完整填滿 2×n 棋盤的方法數。注意是「完全填滿」不是「部分填滿」

推導遞推式

f(n) = 2×f(n-1) + f(n-3)。2×f(n-1) 來自 Tromino 兩個方向各延伸 f(n-1)，f(n-3) 來自純 Domino 組合

滾動計算

f(n) 只依賴 f(n-1) 和 f(n-3)，可用三個變數滾動計算。也可直接用陣列更直觀

取模

每步對 10^9+7 取模，防止乘法中間結果溢位 64 位整數

程式碼

C#

csharp

public class Solution {
    public int NumTilings(int n) {
        const int MOD = 1_000_000_007;
        if (n <= 2) return n;
        
        long[] dp = new long[n + 1];
        dp[0] = 1; dp[1] = 1; dp[2] = 2;
        
        for (int i = 3; i <= n; i++) {
            // f(n) = 2*f(n-1) + f(n-3)
            dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD;
        }
        return (int)dp[n];
    }
}

TypeScript

typescript

function numTilings(n: number): number {
    const MOD = 1_000_000_007;
    if (n <= 2) return n;
    
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1; dp[1] = 1; dp[2] = 2;
    
    for (let i = 3; i <= n; i++) {
        dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD;
    }
    return dp[n];
}

Python

python

def numTilings(n: int) -> int:
    MOD = 10**9 + 7
    if n <= 2:
        return n
    
    dp = [0] * (n + 1)
    dp[0], dp[1], dp[2] = 1, 1, 2
    
    for i in range(3, n + 1):
        dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD
    
    return dp[n]

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(n)（可優化為 O(1)） |

Time：從 3 到 n 線性遍歷，每步只做一次乘法、一次加法和一次取模
Space：用長度 n+1 的陣列存中間結果。若改用三個滾動變數可降到 O(1)

圖解

n=1: 1種

f(n-2)→間接→

n=2: 2種

f(n-1)×2→

n=3: 5種

f(n-1)×2→

n=4: 11種

→

f(n) = 2f(n-1) + f(n-3)

圖表展示了遞推關係：f(4)=11 來自 2×f(3) + f(1) = 2×5 + 1 = 11。公式中 2×f(n-1) 對應 Tromino 上下兩個方向延伸的鋪法，f(n-3) 對應三個直立 Domino 的組合。

進階觀點

💡面試追問

遞推式 f(n) = 2×f(n-1) + f(n-3) 怎麼推導？ 定義兩個狀態：f(n) 是完整填滿 2×n 的方法數，g(n) 是 2×n 加一個突出格的方法數。轉移：f(n) = f(n-1) + f(n-2) + 2×g(n-1)，g(n) = g(n-1) + f(n-2)。消去 g(n) 後化簡得到 f(n) = 2×f(n-1) + f(n-3)。
用兩個 DP 陣列的做法？ 定義 full[n]（完整填滿）和 partial[n]（有一格突出），轉移更直觀：full[n] = full[n-1] + full[n-2] + 2×partial[n-1]，partial[n] = partial[n-1] + full[n-2]。
n 極大時怎麼辦？ f(n) 的遞推涉及 f(n-1)、f(n-3)，可以建構 3×3 轉移矩陣，用矩陣快速冪在 O(log n) 內計算。

邊界情況

n 等於 1：只能放一塊直立 Domino，回傳 1
n 等於 2：兩塊直立或兩塊橫放，共 2 種，回傳 2
n 等於 1000（題目上限）：結果是超大數字，必須每步取模避免溢位。注意 C# 中 2×dp[i-1] 可能超過 int 範圍，建議用 long

理解測驗

🤔 f(n) = 2*f(n-1) + f(n-3) 中的 2*f(n-1) 代表什麼？

🤔 為什麼需要對 10^9+7 取模？