Longest Increasing Path in a Matrix LeetCode solution in Python

1
class Solution:
2
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
3
        ROWS, COLS = len(matrix), len(matrix[0])
4
        dp = {}
5

6
        def dfs(r, c, prevVal):
7
            if r < 0 or r == ROWS or c < 0 or c == COLS or matrix[r][c] <= prevVal:
8
                return 0
9
            if (r, c) in dp:
10
                return dp[(r, c)]
11
            res = 1
12
            res = max(res, 1 + dfs(r + 1, c, matrix[r][c]))
13
            res = max(res, 1 + dfs(r - 1, c, matrix[r][c]))
14
            res = max(res, 1 + dfs(r, c + 1, matrix[r][c]))
15
            res = max(res, 1 + dfs(r, c - 1, matrix[r][c]))
16
            dp[(r, c)] = res
17
            return res
18

19
        for r in range(ROWS):
20
            for c in range(COLS):
21
                dfs(r, c, -1)
22
        return max(dp.values())