2435. 矩陣中能被k整除的路徑

思路

三維動態規劃。

定義f[i][j][remain] = 走到grid[i][j]的，%k = remain的路徑數目。
題目要的就是f[m - 1][n - 1][0]。

假如我現在要走到位置grid[i][j]，能從上面或是左邊走過來。
也就是f[i][j] = f[i][j - 1] + f[i - 1][j]。

但是現在是三維，要更新的是f[i][j][remain]。
想要走到grid[i][j]，且餘數為remain，可以怎麼來？
假設我想要讓餘數為remain = 0，這格的數值grid[i][j] = 3，k = 20，
那麼f[i][j][0] = f[i - 1][j][17] + f[i][j - 1][17]。
因為 % 的關係，我自己用加法會比較好想，所以程式碼會算出新的餘數來更新f矩陣，而不是倒著推回去。

第一個寫法分為三個迴圈，用來更新第一行跟第一列，以及剩下的部分。
第二個寫法則是合併起來，比較簡潔，也比較難懂。

程式碼

1. 動態規劃

class Solution {
public:
    int numberOfPaths(vector<vector<int>>& grid, int k) {
        const int MOD = 1e9 + 7;
        int m = grid.size(), n = grid[0].size();
        // f[i][j][remain] = 走到 grid[i][j], 對 k 取餘數 = remain 的路徑數目。
        vector<vector<vector<int>>> f(m, vector<vector<int>>(n, vector<int>(k, 0)));
        f[0][0][grid[0][0] % k] = 1;
        int newRemain;
        for(int j = 1; j < n; ++j) {
            for(int remain = 0; remain < k; ++remain) {
                newRemain = (remain + grid[0][j]) % k;
                f[0][j][newRemain] = f[0][j - 1][remain];
                f[0][j][newRemain] %= MOD;
            }
        }
        for(int i = 1; i < m; ++i) {
            for(int remain = 0; remain < k; ++remain) {
                newRemain = (remain + grid[i][0]) % k;
                f[i][0][newRemain] = f[i - 1][0][remain];
                f[i][0][newRemain] %= MOD;
            }
        }
        for(int i = 1; i < m; ++i) {
            for(int j = 1; j < n; ++j) {
                for(int remain = 0; remain < k; ++remain) {
                    newRemain = (remain + grid[i][j]) % k;
                    f[i][j][newRemain] += f[i - 1][j][remain] + f[i][j - 1][remain];
                    f[i][j][newRemain] %= MOD;
                }
            }
        }
        return f[m - 1][n - 1][0];
    }
};

2. 動態規劃，壓縮到一個大迴圈

class Solution {
public:
    int numberOfPaths(vector<vector<int>>& grid, int k) {
        const int MOD = 1e9 + 7;
        int m = grid.size(), n = grid[0].size();
        vector<vector<vector<int>>> f(m, vector<vector<int>>(n, vector<int>(k, 0)));

        f[0][0][grid[0][0] % k] = 1;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 && j == 0) continue;
                for (int r = 0; r < k; ++r) {
                    int newRemain = (r + grid[i][j]) % k;
                    long long fromUp = (i > 0 ? f[i - 1][j][r] : 0);
                    long long fromLeft = (j > 0 ? f[i][j - 1][r] : 0);
                    f[i][j][newRemain] = (f[i][j][newRemain] + fromUp + fromLeft) % MOD;
                }
            }
        }

        return f[m - 1][n - 1][0];
    }
};

複雜度分析

• 時間複雜度：$O(mnk)$
• 空間複雜度：$O(mnk)$