題目資訊

題目編號: 1931
題目連結: Painting a Grid With Three Different Colors
主題: Dynamic Programming

題目敘述

你有兩個整數 m 和 n。考慮一個 m x n 的網格，其中每個單元格最初都是白色的。你可以將每個單元格塗成紅色、綠色或藍色。所有單元格都必須被塗色。

返回將網格上色且沒有兩個相鄰的單元格具有相同顏色的方法數量。由於答案可能非常大，請返回它對 $10^9 + 7$ 取模的結果。

範例 1:

範例 1

輸入: m = 1, n = 1
輸出: 3
解釋: 圖像中顯示了三種可能的著色方案。

範例 2:

範例 2

輸入: m = 1, n = 2
輸出: 6
解釋: 圖像中顯示了六種可能的著色方案。

範例 3:

輸入: m = 5, n = 5
輸出: 580986

約束:

$1 \leq m \leq 5$
$1 \leq n \leq 1000$

直覺

問題要求我們找出一個 $ m \times n $ 的網格，以三種顏色塗色，且相鄰的單元格不能有相同顏色的方法數。鑒於限制條件，特別是 $ n $ 可能達到 1000 的大小，直觀的組合方法可能會導致計算複雜度過高。因此，解決方案利用動態規劃，專注於有效的列顏色模式及其之間的轉換。關鍵在於將問題簡化為確定列模式之間的有效狀態轉換，從而簡化了原本考慮整個網格的繁雜任務。

解法

該方法可以分為以下幾個步驟：

單列表示與驗證：
- 由於每個單元格可以選擇三種顏色，每一列可以表示為一個以 3 為基數的數字。列中的單元格數量為 $ m $，因此存在 $ 3^m $ 種可能的列模式。
- 定義函數 isValidSingleColumn 檢查給定的列模式（表示為一個數字）是否有效，即相鄰的單元格不應具有相同顏色。
收集有效的列模式：
- 我們遍歷所有 $ 3^m $ 種可能的列模式，使用 isValidSingleColumn 函數篩選出有效的列模式，並將其與索引一起存儲以便於參考。
列轉換驗證：
- 我們定義另一個函數 isValidColumnPair 來檢查兩列是否可以相鄰而不違反顏色限制。這意味著對於相鄰的兩列，這兩列同一行的單元格不能有相同顏色。
- 使用此函數建立任何兩個有效列之間的有效轉換映射。
動態規劃設置：
- 設置一個二維動態規劃表 dp，其中 $ dp[i][j] $ 表示顏色方式的數量，第一 $ i $ 列的網格以第 $ j $ 個有效列模式結尾。
- 對於第一列，每個有效模式都是一種有效的塗色方式，所以 dp[0] 的所有條目初始化為 1。
填充動態規劃表：
- 對於每個後續的列，我們通過考慮來自前一列的有效轉換來更新動態規劃表： $$ dp[col][currentPatternIndex] = (dp[col][currentPatternIndex] + dp[col - 1][prevPatternIndex]) % MOD $$
- 這些轉換由預計算的列模式之間的有效轉換引導。
最終計算：
- 最後的答案通過對動態規劃表的最後一列求和來獲得，這表示對整個網格的所有有效塗色方式以每個潛在的結束列模式。

此方法有效地封裝了限制條件，並系統地計算出期望結果，其合理的時間由狀態縮減和動態規劃實現。使用模數 $10^9 + 7$ 保證解決方案在大輸出時仍然符合期望的計算限制。

程式碼

C++

#define MOD 1000000007

class Solution {
private:
    // 函數檢查單一列模式是否有效
    bool isValidSingleColumn(int num, int m) {
        int prevColor = -1; // 前一個單元格的顏色

        for (int i = 0; i < m; i++) {
            int currentColor = num % 3; // 當前單元格的顏色

            // 檢查相鄰單元格是否有相同顏色
            if (currentColor == prevColor) 
                return false;

            prevColor = currentColor;
            num /= 3; // 移動到下一個單元格
        }

        return true;
    }

    // 函數檢查兩列是否可以相鄰
    bool isValidColumnPair(int col1, int col2, int m) {
        for (int i = 0; i < m; i++) {
            // 檢查同一行的單元格是否有相同顏色
            if (col1 % 3 == col2 % 3) 
                return false;

            col1 /= 3;
            col2 /= 3;
        }
        return true;
    }

public:
    // 函數返回著色網格的方式數
    int colorTheGrid(int m, int n) {
        vector<int> validSingleColumns;
        unordered_map<int, int> patternToIndex;

        int maxState = pow(3, m); // 單一列的所有可能狀態總數

        // 收集有效的列模式
        for (int i = 0; i < maxState; ++i) {
            if (isValidSingleColumn(i, m)) {
                patternToIndex[i] = validSingleColumns.size();
                validSingleColumns.push_back(i);
            }
        }

        int totalPatterns = validSingleColumns.size();
        vector<vector<int>> validColumnTransitions(totalPatterns);

        // 建立列間的有效轉換
        for (int i = 0; i < totalPatterns; ++i) {
            for (int j = 0; j < totalPatterns; ++j) {
                if (isValidColumnPair(validSingleColumns[i], validSingleColumns[j], m)) {
                    validColumnTransitions[i].push_back(j);
                }
            }
        }

        // 動態規劃表以計算著色方式
        vector<vector<int>> dp(n, vector<int>(totalPatterns, 0));
        
        // 初始基礎情況設置
        for (int j = 0; j < totalPatterns; ++j) 
            dp[0][j] = 1;

        // 填寫DP表格
        for (int col = 1; col < n; ++col) {
            for (int currentPatternIndex = 0; currentPatternIndex < totalPatterns; ++currentPatternIndex) {
                for (int prevPatternIndex : validColumnTransitions[currentPatternIndex]) {
                    dp[col][currentPatternIndex] = (dp[col][currentPatternIndex] + dp[col - 1][prevPatternIndex]) % MOD;
                }
            }
        }

        // 計算最終答案
        int result = 0;
        for (int j = 0; j < totalPatterns; ++j) {
            result = (result + dp[n - 1][j]) % MOD;
        }

        return result;
    }
};

Python

MOD = 1000000007

class Solution:
    # 函數用來檢查單列的模式是否有效
    def isValidSingleColumn(self, num, m):
        prevColor = -1  # 前一個格子的顏色

        for i in range(m):
            currentColor = num % 3  # 當前格子的顏色

            # 檢查相鄰格子是否具有相同顏色
            if currentColor == prevColor:
                return False

            prevColor = currentColor
            num //= 3  # 移動到下一個格子

        return True

    # 函數用來檢查兩列是否可以相鄰
    def isValidColumnPair(self, col1, col2, m):
        for i in range(m):
            # 檢查同一行的格子是否具有相同顏色
            if col1 % 3 == col2 % 3:
                return False

            col1 //= 3
            col2 //= 3
        return True

    # 函數用來返回填滿網格的方法數量
    def colorTheGrid(self, m, n):
        validSingleColumns = []
        patternToIndex = {}

        maxState = pow(3, m)  # 單列所有可能狀態的總數

        # 收集有效的列模式
        for i in range(maxState):
            if self.isValidSingleColumn(i, m):
                patternToIndex[i] = len(validSingleColumns)
                validSingleColumns.append(i)

        totalPatterns = len(validSingleColumns)
        validColumnTransitions = [[] for _ in range(totalPatterns)]

        # 構建列之間的有效轉換
        for i in range(totalPatterns):
            for j in range(totalPatterns):
                if self.isValidColumnPair(validSingleColumns[i], validSingleColumns[j], m):
                    validColumnTransitions[i].append(j)

        # 動態規劃表用來計算填色方法
        dp = [[0] * totalPatterns for _ in range(n)]
        
        # 初始基礎情況設置
        for j in range(totalPatterns):
            dp[0][j] = 1

        # 填充DP表
        for col in range(1, n):
            for currentPatternIndex in range(totalPatterns):
                for prevPatternIndex in validColumnTransitions[currentPatternIndex]:
                    dp[col][currentPatternIndex] = (dp[col][currentPatternIndex] + dp[col - 1][prevPatternIndex]) % MOD

        # 計算最終答案
        result = 0
        for j in range(totalPatterns):
            result = (result + dp[n - 1][j]) % MOD

        return result

複雜度分析

時間複雜度: $O(n \cdot p^2)$，其中 $p = 3^m$。時間複雜度取決於在狀態之間生成和使用有效列轉換。具體來說，這涉及計算每對模式的有效轉換，這導致 $O(p^2)$ 的複雜度。這一過程對每個 $n$ 列進行迴圈，形成整體的複雜度。
空間複雜度: $O(n \cdot p)$。空間複雜度主要來自動態規劃表格，其儲存的是用有效模式上色到每一列的方式數量。DP 表格的尺寸為 $n \times p$，這導致空間使用。額外的空間用於儲存有效模式和轉換，但這部分不會超過 DP 表格的空間。

CS Note
En

Leetcode 1931. Painting a Grid With Three Different Colors

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析