Core Insight A table exposes how two changing prefixes or positions depend on smaller cases.
Common Pitfall Initialize the first row and column before using neighboring cells.
Description
Find the longest increasing path in a matrix.
Constraints
- Time Complexity:
O(m·n) - Space Complexity:
O(m·n)
Tags
arraydynamic-programmingdfsbfsgraphtopological-sortmemoizationmatrix
Implementation Plan Translate the invariant into these small, testable moves.
- Define the row and column meaning.
- Initialize base cases.
- Fill cells in dependency order.
- Read the answer from the target cell.
def longestIncreasingPath(matrix):
ROWS, COLS = len(matrix), len(matrix[0])
dp = {}
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]))
res = max(res, 1 + dfs(r - 1, c, matrix[r][c]))
res = max(res, 1 + dfs(r, c + 1, matrix[r][c]))
res = max(res, 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())