# DFS with memoization in python

• ``````class Solution(object):
def longestIncreasingPath(self, matrix):

def longestIncreasingPathHelper(matrix, table, i, j):
if table[i][j]:
return table[i][j]
pathLength = 1
if i-1 >= 0 and matrix[i-1][j] > matrix[i][j]:
pathLength = max(pathLength,
longestIncreasingPathHelper(matrix, table, i-1, j) + 1)
if i+1 < len(matrix) and matrix[i+1][j] > matrix[i][j]:
pathLength = max(pathLength,
longestIncreasingPathHelper(matrix, table, i+1, j) + 1)
if j-1 >= 0 and matrix[i][j-1] > matrix[i][j]:
pathLength = max(pathLength,
longestIncreasingPathHelper(matrix, table, i, j-1) + 1)
if j+1 < len(matrix[i]) and matrix[i][j+1] > matrix[i][j]:
pathLength = max(pathLength,
longestIncreasingPathHelper(matrix, table, i, j+1) + 1)
table[i][j] = pathLength
return pathLength

if not matrix:
return 0
table = [[0] * len(row) for row in matrix]
max_path = 0
for i in range(len(matrix)):
for j in range(len(matrix[i])):
max_path = max(max_path, longestIncreasingPathHelper(matrix, table, i, j))
return max_path``````

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