# Python DFS with memorization, with explanation

• Brute force is to do a Depth First Search for every cell to find the longest possible path from it.

It can be optimized by realizing that we only need to visit every cell once, memorizing the length of the longest path starting from it. The longest path from a neighboring cell through this cell will be one more.

``````class Solution(object):
def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""

def DFS_longest_dist(r, c):
if longest[r][c]:
# already calculated longest distance from this cell
return longest[r][c]

# init longest distance
longest[r][c] = 1

for move in moves:
r_next, c_next = r + move[0], c + move[1]
if 0 <= r_next < rows and 0 <= c_next < cols and matrix[r][c] < matrix[r_next][c_next]:
# valid move, get longest distance through it, which is
# one more than the longest path starting at the next cell
dist = DFS_longest_dist(r_next, c_next) + 1

# is it better than what we have?
if dist > longest[r][c]:
longest[r][c] = dist

return longest[r][c]

moves = [(0,1),(0,-1),(1,0),(-1,0)]
max_dist = 0

rows = len(matrix)
cols = 0 if not rows else len(matrix[0])

# will store distance for longest path from given cell
# we can use 0 for unvisited because minimum valid dist is 1
longest = [[0] * cols for _ in range(rows)]

# iterate through every cell and calculate longest path through it
for r in range(rows):
for c in range(cols):
if not longest[r][c]:
# haven't calculated longest for r,c yet, so do it
dist = DFS_longest_dist(r,c)
# keep track of max
max_dist = max(max_dist, dist)

return max_dist
``````

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