Leetcode 2435. Paths in Matrix Whose Sum Is Divisible by K
Intuition
Step1: subproblem.
This can be 3D DP: $DP[i][j][k]$ indicate the #(routes) from $[0,0]$ to $[i,j]$ with value k.
Then the goal is to compute the sum of $DP[m-1][n-1][k]$ for any k, then mod $10^9+7$.
Approach
Step2: Write the recrusion. Update from $[0,0]$ to $[m-1,n-1]$!
consider $DP[i][j][k]$ is initially 0.
It accept last step from top: $[i-1,j]$ or left: $[i,j-1]$.
For each k from them: add $grid[i][j]$ and update as a record of $DP[i][j]$
\[DP[i][j][k+grid[i][j]] += DP[i-1][j][k]\] \[DP[i][j][k+grid[i][j]] += DP[i][j-1][k]\]BTW, take care at the index! (For Python code, I use defaultdict with default 0 so it’s safe)
Last, add % for each value to save space and time! here k is very small, you can save a lot of memory!
That’s it!
Complexity
-
Time complexity: $\Theta(mnk)$, and third level iterate can be less than k. Maybe $O(mnk)$ accepted.
-
Space complexity: Version 1: keep $DP[i][j][k]$ -> $\Theta(mnk)$ Space Optimized: only use two lines: last and current. Then you can save a layer! $\Theta(nk)$.
Code
If you want to write a simple version: I am sorry I can only give you key steps from it! I write the simple version at first, but forget to save it, then turn to a space optimized version. But this is not very difficult. Hope you can learn from it!
dp = defaultdict(lambda: defaultdict(lambda: defaultdict(int)))
dp[0][0][grid[0][0]] = 1
A complete version:
class Solution:
def numberOfPaths(self, grid: List[List[int]], k: int) -> int:
mo = 10**9+7
# dp = defaultdict(lambda: defaultdict(lambda: defaultdict(int)))
dp1 = None
dp2 = defaultdict(lambda: defaultdict(int))
m, n = len(grid), len(grid[0])
# dp[0][0][grid[0][0]] = 1
dp2[0][grid[0][0]%k] = 1
for i in range(1,n):
for p1, p2 in dp2[i-1].items():
dp2[i][(p1+grid[0][i])%k] = p2 % mo
for i in range(1,m):
dp1, dp2 = dp2, defaultdict(lambda: defaultdict(int))
for j in range(n):
for t in [dp1[j].items(), dp2[j-1].items()]:
for p1, p2 in t:#dp1[j-1].items():
# if j ==0: continue
newans = (p1+grid[i][j])%k
dp2[j][newans] = (dp2[j][newans]+p2) %mo
ans = 0
for p1,p2 in dp2[n-1].items():
if p1%k==0:
ans =(ans+p2)% mo
return ans
Any Problems?
I recommend to try this one:
3725. Count Ways to Choose Coprime Integers from Rows