Question

Code

class Solution(object):
    def longestIncreasingPath(self, matrix):
        row, col = len(matrix), len(matrix[0])
        dp = {}

        def dfs(r, c, preVal):
            if not ((0 <= r < row) and (0 <= c < col) and( matrix[r][c] > preVal)):
                return 0

            if (r, c) in dp:
                return dp[(r,c)]

            res = 1
            res = max(res, 1 + dfs(r + 1, c, matrix[r][c]))
            res = max(res, 1 + dfs(r - 1, c, matrix[r][c]))
            res = max(res, 1 + dfs(r, c + 1, matrix[r][c]))
            res = max(res, 1 + dfs(r, c - 1, matrix[r][c]))

            dp[(r,c)] = res

            return res

        for r in range(row):
            for c in range(col):
                dfs(r, c, -1)

        return max(dp.values())