題目資訊

• 題目編號: 790
• 題目連結: Domino and Tromino Tiling
• 主題: Dynamic Programming

題目敘述

你有兩種類型的磁磚：一種是 2 x 1 的多米諾骨牌形狀和一種三格骨牌形狀。你可以旋轉這些形狀。

給定一個整數 $n$，返回鋪滿 2 x n 棋盤的方法數。由於答案可能非常大，返回時取 模 $10^9 + 7$。

在鋪設中，每個方格都必須被磁磚覆蓋。只有當棋盤上存在兩個4方向相鄰的方格，且只有其中一種鋪法將它們同時覆蓋時，兩種鋪法才被視為不同。

範例 1:

輸入: n = 3
輸出: 5
解釋: 上述顯示了五種不同的方法。

範例 2:

輸入: n = 1
輸出: 1

限制條件:

• $1 \leq n \leq 1000$

直覺

將一個 $2 \times n$ 的棋盤使用多米諾骨牌和三塊板骨牌進行覆蓋的問題，可以透過動態規劃來解決。主要的觀察是在於，為較小的棋盤大小計算出來的解法數量可以用來推導出較大棋盤的排列。藉由理解多米諾骨牌和三塊板骨牌如何填滿棋盤的不同部分，我們可以從較小的案例中遞歸地建構出解答。遞歸式捕捉到一個 $2 \times n$ 的棋盤可以視為從較小的棋盤（例如，$2 \times (n-1)$、$2 \times (n-2)$、或 $2 \times (n-3)$）延伸而來。這種方法的結果來自於對於根據最後幾塊骨牌擺放所導致的不同配置進行可視化構造。

解法

為了解決這個鋪磚問題，我們採用了動態規劃來計算從 $1$ 到 $n$ 的每個棋盤大小的配置數量，並將結果存儲以避免重複計算。以下是該方法的詳細說明：

1. 基本案例：

   • 當 $n = 1$ 時，只有一種方法可以將 $2 \times 1$ 的棋盤用一個垂直的多米諾骨牌進行鋪設。因此，$dp[1] = 1$。
   • 當 $n = 2$ 時，棋盤可以有兩種方式進行鋪設：要麼是放置兩個並排的垂直多米諾骨牌，要麼是放兩個堆疊的水平多米諾骨牌。因此，$dp[2] = 2$。
   • 當 $n = 3$ 時，出現五種不同的鋪設配置，包括多米諾和三塊板。因此，$dp[3] = 5$。

2. 狀態轉移：

   • 對於任意大小為 $2 \times i$ 的棋盤，其中 $i > 3$，該棋盤可以從以下擴展而來：
     • 一個 $2 \times (i-1)$ 的棋盤，通過在末端添加一個垂直的多米諾骨牌進行擴展。
     • 一個 $2 \times (i-2)$ 的棋盤，通過添加兩個水平的多米諾骨牌來完成 $2 \times 2$ 的區域進行擴展。
     • 一個 $2 \times (i-3)$ 的棋盤，通過添加一個形式的三塊板進行擴展。
   • 遞歸公式為： $$ dp[i] = (2 \times dp[i - 1] + dp[i - 3]) \mod (10^9 + 7) $$

3. 動態規劃陣列構造：

   • 我們初始化一個動態規劃（DP）陣列 dp，其中 dp[i] 代表鋪設一個 $2 \times i$ 棋盤的方法數。
   • 我們利用基本案例事先填充 dp 陣列。
   • 我們從 $i = 4$ 開始疊代到 $n$，應用轉移公式以填充 DP 陣列，獲得每一個後續棋盤大小的結果。

4. 結果計算：

   • 在填充完 DP 陣列後，對於 $2 \times n$ 棋盤的解答存儲在 dp[n] 中。
   • 最後返回 dp[n] 作為最終答案，並於 (10^9 + 7) 取模以處理大數字並防止溢出。

這個方法藉由利用之前計算所得的結果，高效地計算出可能的鋪設配置數量，並透過動態規劃減少了複雜度。

程式碼

C++

class Solution {
    // 定義一個常數 MOD 來處理大數
    int MOD = 1000000007;
    
public:
    int numTilings(int n) {
        // 處理小 n 的基礎案例
        if (n <= 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 5;
        
        // 創建一個動態規劃陣列來儲存結果
        vector<int> dp(n + 1, 0);
        dp[0] = 1; // 有一種方法可以覆蓋 2x0 的板（什麼也不做）
        dp[1] = 1; // 一種方法覆蓋 2x1 的板（使用一個垂直的多米諾骨牌）
        dp[2] = 2; // 兩種方法覆蓋 2x2 的板（兩個垂直的多米諾骨牌或者兩個水平的多米諾骨牌）
        dp[3] = 5; // 之前解釋的五種方法覆蓋 2x3 的板
        
        // 使用動態規劃來填滿 dp 陣列以覆蓋所有到 2xn 的板
        for (int i = 4; i <= n; ++i) {
            // 使用先前計算的值計算 2xi 板的方法數
            dp[i] = ((long long)dp[i - 1] * 2 + (long long)dp[i - 3]) % MOD; 
        }
        
        // 返回對特定輸入 n 的結果
        return dp[n];
    }
};

Python

class Solution:
    # 定義常數以模擬大數運算
    MOD = 1000000007
    
    def numTilings(self, n: int) -> int:
        # 基礎情況處理小的 n
        if n <= 1:
            return 1
        if n == 2:
            return 2
        if n == 3:
            return 5
        
        # 創建動態規劃陣列以存儲結果
        dp = [0] * (n + 1)
        dp[0] = 1  # 有一種方式可以鋪滿一個 2x0 的板子（不做任何動作）
        dp[1] = 1  # 一種方式來鋪滿一個 2x1 的板子（使用一個垂直的多米諾骨牌）
        dp[2] = 2  # 兩種方式來鋪滿一個 2x2 的板子（兩個垂直的多米諾骨牌或兩個水平的多米諾骨牌）
        dp[3] = 5  # 五種方式來鋪滿一個 2x3 的板子，如上所述
        
        # 使用動態規劃來填充所有的 2xn 板子的 dp 陣列
        for i in range(4, n + 1):
            # 使用之前計算的值來計算 2xi 板子的鋪法數量
            dp[i] = (dp[i - 1] * 2 + dp[i - 3]) % self.MOD
        
        # 返回特定輸入 n 的結果
        return dp[n]

複雜度分析

• 時間複雜度: 演算法的時間複雜度是 $O(n)$。這是因為該演算法使用了一個循環，該循環在從 4 到 $n$ 的範圍內迭代，在每次迭代中執行一個恆定量的工作。
• 空間複雜度: 演算法的空間複雜度是 $O(n)$。這是由於動態規劃陣列 dp，其儲存了從 0 到 $n$ 的所有棋盤大小的解。此陣列的長度為 $n+1$，因此空間複雜度為 $O(n)$。