---
# System prepended metadata

title: 2435. Paths in Matrix Whose Sum Is Divisible by K
tags: [Leetcode, Dynamic Programming, Hard]

---

# 2435. Paths in Matrix Whose Sum Is Divisible by K
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/paths-in-matrix-whose-sum-is-divisible-by-k/description/
## 思路
```dp[i][j][a]```表示从```grid[0][0]```走到```grid[i][j]``` path sum%k==a的路径个数
## Code
```java=
class Solution {
    public int numberOfPaths(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        long[][][] dp = new long[m][n][k];
        int mod = 1000000007;
        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 a=0; a<k; a++){
                    if(i!=0 && dp[i-1][j][a]!=0) dp[i][j][(a+grid[i][j]%k)%k] = (dp[i][j][(a+grid[i][j]%k)%k]+dp[i-1][j][a])%mod;
                    if(j!=0 && dp[i][j-1][a]!=0) dp[i][j][(a+grid[i][j]%k)%k] = (dp[i][j][(a+grid[i][j]%k)%k]+dp[i][j-1][a])%mod;
                } 
            }
        }
        return (int)dp[m-1][n-1][0];
    }
}
```