DAG longest path: edges go from lower to higher value.
DFS + memoization:
dfs(r,c) = length of longest increasing path starting at (r,c).
Recurse to neighbors with greater value and memoize results.
Because edges only go to strictly larger values, there are no cycles; memoized DFS gives optimal substructure.
DAG longest path: edges go from lower to higher value.
DFS + memoization:
dfs(r,c) = length of longest increasing path starting at (r,c).
Recurse to neighbors with greater value and memoize results.
Because edges only go to strictly larger values, there are no cycles; memoized DFS gives optimal substructure.