LC 0329 [H] Longest Increasing Path in a Matrix - ALawliet/algorithms GitHub Wiki
even though it's brute force we end up reusing previous cells that we stored so it's still pretty efficient
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
ROWS, COLS = len(matrix), len(matrix[0])
dp = {} # (r, c) -> LIP
def dfs(r, c, prevVal):
if (r < 0 or r == ROWS or c < 0 or c == COLS or matrix[r][c] <= prevVal):
return 0
if (r, c) in dp:
return dp[(r, c)]
res = 1
res = max(res,
1 + dfs(r+1, c, matrix[r][c]),
1 + dfs(r-1, c, matrix[r][c]),
1 + dfs(r, c+1, matrix[r][c]),
1 + dfs(r, c-1, matrix[r][c])
)
dp[(r, c)] = res
return res
for r in range(ROWS):
for c in range(COLS):
dfs(r, c, -1)
return max(dp.values())