# Top Down DP Solution in python

• ``````    def _within_bounds(self, row, col, rows, cols):
return 0 <= row < rows and 0 <= col < cols

def _calc_lip(self, matrix, row, col, LIP):
if LIP[row][col] != 0:
return LIP[row][col]

LIP[row][col] = 1
rows = len(matrix)
cols = len(matrix[0])

for row_disp, col_disp in [(0,1),(0,-1),(1,0),(-1,0)]:
dest_row = row + row_disp
dest_col = col + col_disp
if not self._within_bounds(dest_row, dest_col, rows, cols):
continue

if matrix[dest_row][dest_col] < matrix[row][col]:
LIP[row][col] = max(LIP[row][col], 1 + self._calc_lip(matrix, dest_row, dest_col, LIP))

return LIP[row][col]

def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
if not matrix:
return 0

rows = len(matrix)
cols = len(matrix[0])
max_lip = 1
LIP = [[0 for j in xrange(cols)] for i in xrange(rows)]

for row in xrange(rows):
for col in xrange(cols):
max_lip = max(max_lip, self._calc_lip(matrix, row, col, LIP))

return max_lip``````

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