What is the main DP pattern used in Paths in Matrix Whose Sum Is Divisible by K?

The problem uses state transition dynamic programming where the DP state tracks remainders modulo k at each cell.

Can I reduce space complexity in this problem?

Yes, you can optimize from O(m*n*k) to O(n*k) by keeping only the current and previous row of the DP table.

Why do we track remainders instead of the sum?

Tracking remainders avoids large numbers and ensures correctness for checking divisibility by k at each step.

How do we handle the modulo 10^9 + 7 requirement?

Apply modulo 10^9 + 7 after each addition to prevent integer overflow in the DP counts.

Does the actual value of grid elements matter for the DP pattern?

No, only the remainder of each element modulo k matters for state transitions and counting valid paths.

#2435

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你一个下标从 0 开始的 m x n 整数矩阵 grid 和一个整数 k 。你从起点 (0, 0) 出发，每一步只能往下或者往右，你想要到达终点 (m - 1, n - 1) 。请你返回路径和能被 k 整除的路径数目，由于答案可能很大，返回答案对 10 9 + 7 取余的结果。示例 …

数组动态规划矩阵

题目描述

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

请你返回路径和能被 k 整除的路径数目，由于答案可能很大，返回答案对 10⁹ + 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⁴
1 <= m * n <= 5 * 10⁴
0 <= grid[i][j] <= 100
1 <= k <= 50

lightbulb

解题思路

方法一：动态规划

我们记题目中的 $k$ 为 $K$ ，矩阵 $\textit{grid}$ 的行数和列数分别为 $m$ 和 $n$ 。

定义 $f[i][j][k]$ 表示从起点 $(0, 0)$ 出发，到达位置 $(i, j)$ ，且路径上元素和对 $K$ 取模等于 $k$ 的路径数目。初始时， $f[0][0][\textit{grid}[0][0] \bmod K] = 1$ 。最终答案即为 $f[m - 1][n - 1][0]$ 。

我们可以得到状态转移方程：

f[i][j][k] = f[i - 1][j][(k - \textit{grid}[i][j])\bmod K] + f[i][j - 1][(k - \textit{grid}[i][j])\bmod K]

为了避免负数取模的问题，我们可以将上式中的 $(k - \textit{grid}[i][j])\bmod K$ 替换为 $((k - \textit{grid}[i][j] \bmod K) + K) \bmod K$ 。

答案即为 $f[m - 1][n - 1][0]$ 。

时间复杂度 $O(m \times n \times K)$ ，空间复杂度 $O(m \times n \times K)$ 。其中 $m$ 和 $n$ 分别是矩阵 $\textit{grid}$ 的行数和列数，而 $K$ 是题目中的整数 $k$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def numberOfPaths(self, grid: List[List[int]], K: int) -> int:
        mod = 10**9 + 7
        m, n = len(grid), len(grid[0])
        f = [[[0] * K for _ in range(n)] for _ in range(m)]
        f[0][0][grid[0][0] % K] = 1
        for i in range(m):
            for j in range(n):
                for k in range(K):
                    k0 = ((k - grid[i][j] % K) + K) % K
                    if i:
                        f[i][j][k] += f[i - 1][j][k0]
                    if j:
                        f[i][j][k] += f[i][j - 1][k0]
                    f[i][j][k] %= mod
        return f[m - 1][n - 1][0]

speed

复杂度分析

指标	值
时间	complexity is O(m * n * k) since each of the mn cells updates k remainders. Space complexity is O(m n * k), which can be optimized to O(n * k) by reusing rows.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Are you tracking the remainder sums rather than absolute sums to avoid overflow?
question_mark
Can you optimize space by reducing one dimension in the DP array?
question_mark
How do you handle combining paths from both top and left neighbors for all remainders?

warning

常见陷阱

外企场景

error
Forgetting to take modulo k at each step leads to incorrect remainder tracking.
error
Ignoring the modulo 10^9 + 7 for the final result can cause integer overflow.
error
Not correctly initializing the starting cell's remainder can miss valid paths.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Counting paths where the product of elements modulo k equals zero instead of sum.
arrow_right_alt
Allowing diagonal moves and updating the DP state accordingly.
arrow_right_alt
Finding maximum or minimum sum paths divisible by k rather than counting them.

help

常见问题

外企场景

继续练习

#2328 网格图中递增路径的数目 #2556 二进制矩阵中翻转最多一次使路径不连通 #2304 网格中的最小路径代价