Leetcode Problem 2435. Paths in Matrix Whose Sum Is Divisible by K

2435. Paths in Matrix Whose Sum Is Divisible by K

Leetcode Solutions

Dynamic Programming withD Memoization

  1. Initialize a 3D array dp with dimensions [m][n][k] and fill it with zeros.
  2. Set dp[0][0][grid[0][0] % k] to 1, as there is one path to the starting cell with the remainder of the first cell's value modulo k.
  3. Iterate over the grid starting from the top-left corner to the bottom-right corner.
  4. For each cell (i, j), iterate over all possible remainders r from 0 to k-1.
  5. Add the number of paths from the cell above (i-1, j) and the cell to the left (i, j-1) that have a remainder r when their path sums are divided by k.
  6. Update the dp[i][j][(grid[i][j] + r) % k] with the sum of these paths, modulo 10^9 + 7 to prevent integer overflow.
  7. After filling the dp array, return the value of dp[m-1][n-1][0], which represents the number of paths that reach the bottom-right corner with a sum divisible by k.
UML Thumbnail

Recursive DFS with Memoization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...