Problem statement

https://binarysearch.com/problems/Particular-Paths/

Solution

Use dp with states (x, y, current sum).

Complexity

It is O(nm*(n + m)) for time and O(mn) for space.

Code

class Solution:
    def solve(self, M, k):
        m, n = len(M), len(M[0])
        @lru_cache(None)
        def dp(x, y, s):
            if x < 0 or y < 0: return 0
            if x == 0 and y == 0: return int(s == M[0][0])
            return (dp(x, y - 1, s - M[x][y]) + dp(x - 1, y, s - M[x][y])) % (10**9 + 7)

        return dp(m - 1, n - 1, k)