【Leetcode Daily】2435矩阵中和能被K整除的路径

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个二维数组和一个数字 k，求从数组的左上角走到右下角的路径和能被数字 k 整除的个数。

思路分享

• 记忆化搜索到递推，再到空间优化，思路上没什么好总结的，但确实有细节需要注意。

  https://leetcode.cn/problems/paths-in-matrix-whose-sum-is-divisible-by-k/solutions/1878910/dong-tai-gui-hua-pythonjavacgo-by-endles-94wq/?envType=daily-question&envId=2025-11-26

• python 中不太需要考虑数字溢出的问题，但需要考虑内存溢出，可以在 dfs完成后，执行他的 cache_clear 方法来避免溢出。

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:
        # 空间优化
        m, n = len(grid), len(grid[0])
        MOD = 1_000_000_007

        f = [[0]*k for _ in range(n+1)]
        f[1][0] = 1
        new_f = [0]*k
        for i in range(m):
            for j in range(n):
                for val in range(k):
                    next_val = (val+grid[i][j])%k
                    new_f[val] = (f[j+1][next_val] + f[j][next_val]) % MOD
                f[j+1][:] = new_f
        return f[n][0]

        # 递推
        m, n = len(grid), len(grid[0])
        MOD = 1_000_000_007

        f = [[[0]*k for _ in range(n+1)] for _ in range(m+1)]
        f[1][0][0] = 1
        
        for i in range(m):
            for j in range(n):
                for val in range(k):
                    next_val = (val+grid[i][j])%k
                    f[i+1][j+1][val] = (f[i][j+1][next_val] + f[i+1][j][next_val]) % MOD
        return f[m][n][0]
                    
        # 记忆化搜索， 最后一个检查样例的超出内存限制
        m, n = len(grid), len(grid[0])
        MOD = 1_000_000_007
        @cache
        def dfs(i:int, j:int, val:int)->int:
            if i < 0 or j < 0:
                return 0
            
            val += grid[i][j]
            val %= k
            # print(i, j, val)
            if i == 0 and j == 0 and val == 0:
                return 1 
            
            return (dfs(i-1, j, val) + dfs(i, j-1, val))% MOD
        ans = dfs(m-1, n-1, 0)
        dfs.cache_clear()
        return ans