Longest Increasing Path in a Matrix

The key idea is to use cache, which later will be revisited!

class Solution(object):
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        if matrix == [] or matrix ==[[]]:
            return 0

        m = len(matrix)
        n = len(matrix[0])
        dp = [[0 for i in range(n)] for j in range(m)]
        self.directions = [[1,0], [-1,0], [0,-1], [0,1]]
        self.long = 0

        def dfs(i, j, m, n, matrix):
            if dp[i][j] > 0:
                return dp[i][j]

            tmp = 1
            for dir in self.directions:
                x, y = i + dir[0], j + dir[1]
                if x < 0 or y < 0 or x >= m or y >= n or matrix[x][y] <= matrix[i][j]:
                    continue

                path = dfs(x, y, m, n, matrix) + 1
                tmp = max(tmp, path)

            dp[i][j] = tmp
            return tmp

        for i in range(m):
            for j in range(n):
                path = dfs(i, j, m, n, matrix)
                self.long = max(self.long, path)

        return self.long