Number of Increasing Paths in a Grid LeetCode solution in Python

1
# Runtime: 2506 ms (Top 21.4%) | Memory: 118.67 MB (Top 7.1%)
2

3

4
class Solution:
5
    def __init__(self):
6
        self.dp = None
7
        self.di = [0, 0, -1, 1]
8
        self.dj = [-1, 1, 0, 0]
9
        self.mod = 1000000007
10

11
    def countPaths(self, grid):
12
        n = len(grid)
13
        m = len(grid[0])
14
        self.dp = [[0] * m for _ in range(n)]
15
        ans = 0
16
        for i in range(n):
17
            for j in range(m):
18
                ans = (ans + self.dfs(grid, i, j, -1)) % self.mod
19
        return ans
20

21
    def dfs(self, grid, i, j, prev):
22
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] <= prev:
23
            return 0
24
        if self.dp[i][j] != 0:
25
            return self.dp[i][j]
26
        self.dp[i][j] = 1
27
        for k in range(4):
28
            self.dp[i][j] += self.dfs(grid, i + self.di[k], j + self.dj[k], grid[i][j])
29
            self.dp[i][j] %= self.mod
30
        return self.dp[i][j] % self.mod