【动态规划】矩阵中和能被 K 整除的路径【力扣第 314 场周赛】

题目

6203. 矩阵中和能被 K 整除的路径

---

给你一个下标从 0 开始的 m x n 整数矩阵 grid 和一个整数 k 。你从起点 (0, 0) 出发，每一步只能往 下 或者往 右 ，你想要到达终点 (m - 1, n - 1) 。

请你返回路径和能被 k 整除的路径数目，由于答案可能很大，返回答案对 10^9 + 7 取余 的结果。

示例 1：

输入：grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
输出：2
解释：有两条路径满足路径上元素的和能被 k 整除。
第一条路径为上图中用红色标注的路径，和为 5 + 2 + 4 + 5 + 2 = 18 ，能被 3 整除。
第二条路径为上图中用蓝色标注的路径，和为 5 + 3 + 0 + 5 + 2 = 15 ，能被 3 整除。

示例 2：

输入：grid = [[0,0]], k = 5
输出：1
解释：红色标注的路径和为 0 + 0 = 0 ，能被 5 整除。

示例 3：

输入：grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
输出：10
解释：每个数字都能被 1 整除，所以每一条路径的和都能被 k 整除。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 5 * 10^4
• 1 <= m * n <= 5 * 10^4
• 0 <= grid[i][j] <= 100
• 1 <= k <= 50

解题

方法一：动态规划

思路

找出矩阵中所有（符合条件的）路径，经典的动态规划问题：

• 状态定义：$dp[i][j][x]$ 表示从 $(0, 0)$ 走到 $(i, j)$ 时，路径和与 $k$ 取模正好等于 $x$ 的路径数量。
• 状态转移方程：$dp[i][j][(x + grid[i][j]) \mod k] = dp[i - 1][j][x] + dp[i][j - 1][x]$。
• 初始状态：$dp[0][0][grid[0][0] \mod k] = 1$。

那么要求的答案：从 $(0, 0)$ 走到 $(m - 1, n - 1)$ 的所有路径和中能被 $k$ 整除的数量为：$dp[m - 1][n - 1][0]$。

注意：

• 状态转移会从上方和左方同时进行，为例避免下标越界，第一列和第一行要单独处理。
• 为防止溢出，每次更新答案时都要对 $10^9+7$ 进行取模。

代码

class Solution {
    static final int MOD = (int) 1e9 + 7;

    public int numberOfPaths(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        long[][][] dp = new long[m][n][k];
        dp[0][0][grid[0][0] % k] = 1;
        for (int i = 1; i < m; ++i) {
            for (int x = 0; x < k; ++x) dp[i][0][(x + grid[i][0]) % k] = dp[i - 1][0][x] % MOD;
        }
        for (int i = 1; i < n; ++i) {
            for (int x = 0; x < k; ++x) dp[0][i][(x + grid[0][i]) % k] = dp[0][i - 1][x] % MOD;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (i == 0 && j == 0) continue;
                for (int x = 0; x < k; ++x) {
                    dp[i][j][(x + grid[i][j]) % k] = (dp[i - 1][j][x] + dp[i][j - 1][x]) % MOD;
                }
            }
        }
        return (int) dp[m - 1][n - 1][0];
    }
}

把动规数组多开一行一列，下标加一，可以简化代码：

class Solution {
    static final int MOD = (int) 1e9 + 7;

    public int numberOfPaths(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        long[][][] dp = new long[m + 1][n + 1][k];
        dp[1][1][grid[0][0] % k] = 1;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (i == 1 && j == 1) continue;
                for (int x = 0; x < k; ++x) {
                    dp[i][j][(x + grid[i - 1][j - 1]) % k] = (dp[i - 1][j][x] + dp[i][j - 1][x]) % MOD;
                }
            }
        }
        return (int) dp[m][n][0];
    }
}