Leetcode 2435. Paths in Matrix Whose Sum Is Divisible by K

[Woodyiiiiiii]

这道题很显然用DP。而且根据mn的范围来看，估计要mn*k的时间复杂度。这是一道三维数组DP题，即DP数组为dp[m][n][k]。

问题是，DP数组该存什么值，还有状态转化方程。

这里我们直接把dp[i][j][z]等同于所有之前i和j数值之和的余数为z的个数。状态转化方程可以用逆推，(x + cur) % k = z;则求x值的方程为dp[i][j][z] += dp[i - 1][j][(z + k - cur) % k]。

可以看出题目中有除数k的，要善用%。

class Solution {
    public int numberOfPaths(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int[][][] dp = new int[m][n][k];
        int mod = 1000000007;
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int cur = grid[i][j] % k;
                if (i == 0 && j == 0) {
                    dp[i][j][cur] = 1;
                    continue;
                }
                
                for (int z = 0; z < k; ++z) {
                    // (x + cur) % k = z;
                    if (i > 0) {
                        dp[i][j][z] += dp[i - 1][j][(z + k - cur) % k];
                        dp[i][j][z] %= mod;
                    }
                    if (j > 0) {
                        dp[i][j][z] += dp[i][j - 1][(z + k - cur) % k];
                        dp[i][j][z] %= mod;
                    }
                }
            }
        }
        
        return dp[m - 1][n - 1][0];
    }
}

---

• https://leetcode.com/problems/paths-in-matrix-whose-sum-is-divisible-by-k/