Python DFS + Memorization O(mn)


  • 0
    D
    class Solution(object):
        def longestIncreasingPath(self, matrix):
            if not matrix or not matrix[0]:
                return 0
            dp = dict()
            for i in range(len(matrix)):
                for j in range(len(matrix[0])):
                    self.dfs(matrix, i, j, dp)
            return max(dp.values())
        
        def dfs(self, matrix, i, j, dp):
            key = i * len(matrix[0]) + j
            if key in dp:
                return dp[key]
            res = 1
            x, y = [-1, 1, 0, 0], [0, 0, -1, 1]
            for k in range(4):
                xx, yy = i + x[k], j + y[k]
                if xx >= 0 and xx < len(matrix) and yy >= 0 and yy < len(matrix[0]) and matrix[xx][yy] > matrix[i][j]:
                    res = max(res, 1 + self.dfs(matrix, xx, yy, dp))
            dp[key] = res
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.