目标
给你一个下标从 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
思路
有一个矩阵 grid，从左上角出发，只能向下或向右走，求到达右下角的路径中，路径和能被 k 整除的路径数目。
定义 dp[i][j][r] 表示从 (0, 0) 到达 (i, j) 的路径和 模 k 余 r 的路径总数，状态转移方程为 dp[i][j][r] = (dp[i - 1][j][(r + k - rem) % k] + dp[i][j - 1][(r + k - rem) % k]) % mod，其中 rem = grid[i][j] % k。
代码
/**
* @date 2025-11-26 8:49
*/
public class NumberOfPaths2435 {
public int numberOfPaths(int[][] grid, int k) {
int m = grid.length;
int n = grid[0].length;
int mod = 1000000007;
int[][][] dp = new int[m][n][k];
int sum = 0;
for (int i = 0; i < m; i++) {
sum += grid[i][0];
dp[i][0][sum % k] = 1;
}
sum = 0;
for (int j = 0; j < n; j++) {
sum += grid[0][j];
dp[0][j][sum % k] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
int rem = grid[i][j] % k;
for (int r = 0; r < k; r++) {
dp[i][j][r] = (dp[i - 1][j][(r + k - rem) % k] + dp[i][j - 1][(r + k - rem) % k]) % mod;
}
}
}
return dp[m - 1][n - 1][0];
}
}
性能
