# Standard DFS Python solution w/ memorization

• It's a post-order DFS (Divide Conquer) that traverses all possible paths and caches traversed path to avoid duplicated recursion.

``````class Solution(object):
def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
self.directions = [[0, -1], [0, 1], [-1, 0], [1, 0]]
visited = [[0 for j in xrange(0, len(matrix[0]))] for i in xrange(0, len(matrix))]
cachePath = [[-1 for j in xrange(0, len(matrix[0]))] for i in xrange(0, len(matrix))]
maxLength = 0
for i in xrange(0, len(matrix)):
for j in xrange(0, len(matrix[0])):
visited[i][j] = 1
maxLength = max(maxLength, self.dfsHelper(visited, cachePath, i, j, matrix[i][j], matrix))
visited[i][j] = 0
return maxLength

def dfsHelper(self, visited, cachePath, i, j, path, matrix):
if i >= len(matrix) or i < 0 or j >= len(matrix[0]) or j < 0:
return 0
if cachePath[i][j] != -1:
return cachePath[i][j]
maxLength = 0
for d in self.directions:
newi, newj = i + d[0], j + d[1]
if newi >= len(matrix) or newi < 0 or newj >= len(matrix[0]) or newj < 0:
continue
if visited[newi][newj] == 0 and matrix[newi][newj] > path:
visited[newi][newj] = 1
maxLength = max(maxLength, self.dfsHelper(visited, cachePath, newi, newj,  matrix[newi][newj], matrix))
visited[newi][newj] = 0

length = 1 + maxLength
cachePath[i][j] = length
return length``````

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