跳转至

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

题目描述

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

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

解法

方法一：动态规划

我们记题目中的 \(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
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]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int numberOfPaths(int[][] grid, int K) {
        final int mod = (int) 1e9 + 7;
        int m = grid.length, n = grid[0].length;
        int[][][] f = new int[m][n][K];
        f[0][0][grid[0][0] % K] = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < K; ++k) {
                    int k0 = ((k - grid[i][j] % K) + K) % K;
                    if (i > 0) {
                        f[i][j][k] = (f[i][j][k] + f[i - 1][j][k0]) % mod;
                    }
                    if (j > 0) {
                        f[i][j][k] = (f[i][j][k] + f[i][j - 1][k0]) % mod;
                    }
                }
            }
        }
        return f[m - 1][n - 1][0];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int numberOfPaths(vector<vector<int>>& grid, int K) {
        const int mod = 1e9 + 7;
        int m = grid.size(), n = grid[0].size();
        int f[m][n][K];
        memset(f, 0, sizeof(f));
        f[0][0][grid[0][0] % K] = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < K; ++k) {
                    int k0 = ((k - grid[i][j] % K) + K) % K;
                    if (i > 0) {
                        f[i][j][k] = (f[i][j][k] + f[i - 1][j][k0]) % mod;
                    }
                    if (j > 0) {
                        f[i][j][k] = (f[i][j][k] + f[i][j - 1][k0]) % mod;
                    }
                }
            }
        }
        return f[m - 1][n - 1][0];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func numberOfPaths(grid [][]int, K int) int {
    const mod = 1e9 + 7
    m, n := len(grid), len(grid[0])
    f := make([][][]int, m)
    for i := range f {
        f[i] = make([][]int, n)
        for j := range f[i] {
            f[i][j] = make([]int, K)
        }
    }
    f[0][0][grid[0][0]%K] = 1
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            for k := 0; k < K; k++ {
                k0 := ((k - grid[i][j]%K) + K) % K
                if i > 0 {
                    f[i][j][k] = (f[i][j][k] + f[i-1][j][k0]) % mod
                }
                if j > 0 {
                    f[i][j][k] = (f[i][j][k] + f[i][j-1][k0]) % mod
                }
            }
        }
    }
    return f[m-1][n-1][0]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function numberOfPaths(grid: number[][], K: number): number {
    const mod = 1e9 + 7;
    const m = grid.length;
    const n = grid[0].length;
    const f: number[][][] = Array.from({ length: m }, () =>
        Array.from({ length: n }, () => Array(K).fill(0)),
    );
    f[0][0][grid[0][0] % K] = 1;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            for (let k = 0; k < K; ++k) {
                const k0 = (k - (grid[i][j] % K) + K) % K;
                if (i > 0) {
                    f[i][j][k] = (f[i][j][k] + f[i - 1][j][k0]) % mod;
                }
                if (j > 0) {
                    f[i][j][k] = (f[i][j][k] + f[i][j - 1][k0]) % mod;
                }
            }
        }
    }
    return f[m - 1][n - 1][0];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
impl Solution {
    pub fn number_of_paths(grid: Vec<Vec<i32>>, K: i32) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let m = grid.len();
        let n = grid[0].len();
        let K = K as usize;
        let mut f = vec![vec![vec![0; K]; n]; m];
        f[0][0][grid[0][0] as usize % K] = 1;
        for i in 0..m {
            for j in 0..n {
                for k in 0..K {
                    let k0 = ((k + K - grid[i][j] as usize % K) % K) as usize;
                    if i > 0 {
                        f[i][j][k] = (f[i][j][k] + f[i - 1][j][k0]) % MOD;
                    }
                    if j > 0 {
                        f[i][j][k] = (f[i][j][k] + f[i][j - 1][k0]) % MOD;
                    }
                }
            }
        }
        f[m - 1][n - 1][0]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int NumberOfPaths(int[][] grid, int k) {
        const int mod = (int) 1e9 + 7;
        int m = grid.Length, n = grid[0].Length;
        int[,,] f = new int[m, n, k];
        f[0, 0, grid[0][0] % k] = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int p = 0; p < k; ++p) {
                    int k0 = ((p - grid[i][j] % k) + k) % k;
                    if (i > 0) {
                        f[i, j, p] = (f[i, j, p] + f[i - 1, j, k0]) % mod;
                    }
                    if (j > 0) {
                        f[i, j, p] = (f[i, j, p] + f[i, j - 1, k0]) % mod;
                    }
                }
            }
        }
        return f[m - 1, n - 1, 0];
    }
}

评论