Hard

题目描述

给你一个 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

解题思路

这是一道典型的动态规划问题，需要统计路径和能被 k 整除的路径数。

核心思路： 由于只关心路径和是否能被 k 整除，我们只需要关注路径和对 k 的余数。定义 dp[i][j][r] 表示从起点 (0,0) 到位置 (i,j) 的路径中，路径和对 k 取余为 r 的路径数量。

状态转移：

  • 初始状态：dp[0][0][grid[0][0] % k] = 1
  • 转移方程：dp[i][j][r] = dp[i-1][j][(r - grid[i][j] % k + k) % k] + dp[i][j-1][(r - grid[i][j] % k + k) % k]

这里需要注意处理负数取余的情况，使用 (r - val + k) % k 确保结果为正。

优化空间： 由于每个位置只依赖于上方和左方的状态，可以使用滚动数组优化空间复杂度。

答案： 最终答案为 dp[m-1][n-1][0]，即到达终点且路径和对 k 取余为 0 的路径数。

时间复杂度为 O(m × n × k)，空间复杂度可优化至 O(n × k)。

代码实现

class Solution {
public:
    int numberOfPaths(vector<vector<int>>& grid, int k) {
        const int MOD = 1e9 + 7;
        int m = grid.size(), n = grid[0].size();
        
        // dp[i][j][r] 表示到达(i,j)且路径和模k为r的路径数
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(k, 0)));
        
        dp[0][0][grid[0][0] % k] = 1;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;
                
                for (int r = 0; r < k; r++) {
                    int prev_r = (r - grid[i][j] % k + k) % k;
                    
                    if (i > 0) {
                        dp[i][j][r] = (dp[i][j][r] + dp[i-1][j][prev_r]) % MOD;
                    }
                    if (j > 0) {
                        dp[i][j][r] = (dp[i][j][r] + dp[i][j-1][prev_r]) % MOD;
                    }
                }
            }
        }
        
        return dp[m-1][n-1][0];
    }
};

class Solution:
    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:
        MOD = 10**9 + 7
        m, n = len(grid), len(grid[0])
        
        # dp[i][j][r] 表示到达(i,j)且路径和模k为r的路径数
        dp = [[[0] * k for _ in range(n)] for _ in range(m)]
        
        dp[0][0][grid[0][0] % k] = 1
        
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue
                
                for r in range(k):
                    prev_r = (r - grid[i][j] % k) % k
                    
                    if i > 0:
                        dp[i][j][r] = (dp[i][j][r] + dp[i-1][j][prev_r]) % MOD
                    if j > 0:
                        dp[i][j][r] = (dp[i][j][r] + dp[i][j-1][prev_r]) % MOD
        
        return dp[m-1][n-1][0]

public class Solution {
    public int NumberOfPaths(int[][] grid, int k) {
        const int MOD = 1000000007;
        int m = grid.Length, n = grid[0].Length;
        
        // dp[i][j][r] 表示到达(i,j)且路径和模k为r的路径数
        int[,,] dp = new int[m, n, k];
        
        dp[0, 0, grid[0][0] % k] = 1;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;
                
                for (int r = 0; r < k; r++) {
                    int prevR = (r - grid[i][j] % k + k) % k;
                    
                    if (i > 0) {
                        dp[i, j, r] = (dp[i, j, r] + dp[i-1, j, prevR]) % MOD;
                    }
                    if (j > 0) {
                        dp[i, j, r] = (dp[i, j, r] + dp[i, j-1, prevR]) % MOD;
                    }
                }
            }
        }
        
        return dp[m-1, n-1, 0];
    }
}

var numberOfPaths = function(grid, k) {
    const MOD = 1000000007;
    const m = grid.length;
    const n = grid[0].length;

    // dp[i][j][r] = number of paths to (i,j) with sum % k = r
    const dp = Array(m).fill().map(() =>
        Array(n).fill().map(() => Array(k).fill(0))
    );

    dp[0][0][grid[0][0] % k] = 1;

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            for (let r = 0; r < k; r++) {
                if (dp[i][j][r] === 0) continue;

                // Move right
                if (j + 1 < n) {
                    const newR = (r + grid[i][j + 1]) % k;
                    dp[i][j + 1][newR] = (dp[i][j + 1][newR] + dp[i][j][r]) % MOD;
                }

                // Move down
                if (i + 1 < m) {
                    const newR = (r + grid[i + 1][j]) % k;
                    dp[i + 1][j][newR] = (dp[i + 1][j][newR] + dp[i][j][r]) % MOD;
                }
            }
        }
    }

    return dp[m - 1][n - 1][0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(m × n × k)
空间复杂度O(m × n × k)

说明：

  • 时间复杂度：需要遍历所有位置 (m × n)，对每个位置遍历所有可能的余数 k
  • 空间复杂度：三维 dp 数组的大小为 m × n × k
  • 可以优化空间复杂度至 O(n × k) 使用滚动数组

相关题目