1411. Number of Ways to Paint N*3 Grid

https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid?envType=daily-question&envId=2026-01-03

第一個在 leetcode 寫到的 Hard 題目，我覺得這題不算是很難想出解法的類型，他難的是如何寫出一個不會 TLE 的 code。

看到題目我的第一個想法是遞迴，但純用遞迴的話妥妥的 TLE 了，n = 5000 完全扛不住，畢竟類似的 pattern 多做了好幾次。參考提示後，使用 dp[][][][] 來用空間換取時間，就可以剪枝來減少可能百分之九十的遞迴。

程式碼如下。自以為很完美，結果 summit 出去才 beat 5% 哈哈...當時的我真的想不到我的算法還有哪裡可以優化的，因此到了討論區看別人的做法。

class Solution {

public:
    static const int MOD = 1000000007;

    int numOfWays(int n) {
        vector dp(n, vector(3, vector(3, vector<int>(3, -1))));
        vector<int> dummy = {3, 3, 3};
        return compute(n, 0, dummy, dp);
    }

    int compute(int n, int cur_n, vector<int>& last, vector<vector<vector<vector<int>>>>& dp) {

        if (cur_n == n) {
            dp[cur_n -1][last[0]][last[1]][last[2]] = 1;
            return 1;
        }

        long long ans = 0;
        
        for (int i = 0; i < 3; i++) {
            if (i == last[0]) continue;
            for (int j = 0; j < 3; j++) {
                if (j == i || j == last[1]) continue;
                for (int k = 0; k < 3; k++) {
                    if (k == j || k == last[2]) continue;
                    vector<int> cur = {i, j, k};

                    if (dp[cur_n][i][j][k] != -1)
                        ans += dp[cur_n][i][j][k];
                    else
                        ans += compute(n, cur_n + 1, cur, dp);
                }
            }
        }
        
        ans %= MOD;
        if(cur_n != 0) {
            dp[cur_n-1][last[0]][last[1]][last[2]] = ans;
        }
        return ans;
    }
};

Best Solution

看到的當下真的是腦袋當機了，A 是什麼？B 又是什麼？作者有解釋，但我愣是看不懂他在說什麼，看到有別人提出 A 跟 B 個是兩種 pattern，就著這句話我再回頭看題目的 description 就有了新的見解！

A 是 XYZ 的這種 pattern，B 是 XYX。基於這兩種 pattern 會再各自產生出 2XYX+2XYZ 以及 3XYX+2XYZ。然後就這樣一直乘下去！

基本上是排列組合的概念，他去觀察了基於這兩個 pattern 會產生出的結果，並且把它做個 summary 歸納出規律！我覺得蠻厲害的，能夠想到這樣解法的人對於數學應該蠻敏銳的，可惜我不是這個人嗚嗚嗚。

class Solution {
public:
    int numOfWays(int n) {
        const int MOD = 1000000007;
        long long A = 6, B = 6; // n = 1
        
        // XYZ: 2*2*2 - 1 * 2 - 1 * 2 = 4 // 2*XYX 2*XYZ
        // XYX: 2*2*2 - 1 * 2 - 1 * 2 + 1 = 5 // 3*XYX 2*XYZ

        // A: XYZ
        // B: XYX

        for (int i = 2; i <= n; i++) {
            long long newA = (2 * A + 2 * B) % MOD;
            long long newB = (2 * A + 3 * B) % MOD;
            A = newA;
            B = newB;
        }

        return (A + B) % MOD;
    }
};