The problem
Given an integer matrix, return the length of the longest path of strictly increasing values, moving up/down/left/right.
Stuck? Reveal hints one at a time
How to approach it
- 1Define dp(r, c) = longest increasing path STARTING at (r, c).
- 2dp(r, c) = 1 + max(dp of each neighbor with a strictly larger value), or 1 if none.
- 3Memoize dp in a matrix so each cell is computed once.
- 4Answer = max dp over all cells.
Key insight
Increasing values impose a topological order for free — memoized DFS IS dynamic programming over that hidden DAG, no explicit sort needed.
The solution
Watch out for
- No visited set is needed — strict increase already prevents revisiting; adding one breaks correctness.
- Without memoization the same subpaths recompute exponentially.