Problem context and objectives
Mission briefing
Dungeon strategy engineer · A robot must cross a tiled dungeon
Store enough solved tile states to plan the complete route: The Ascending Matrix.
A greedy step can trap the robot; recomputing every route is too expensive.
How you win
- 1Recognize when Longest increasing path matches the clues
- 2Keep this true after every move: memo[cell] is the exact longest increasing path beginning at that cell
- 3Reach the result within O(rows times cols) time and space
Rules and pressure
- Target cost: O(rows times cols) time and space
- State rule: memo[cell] is the exact longest increasing path beginning at that cell
Lesson 1 of 3
Live algorithm trace
Longest increasing path
Complete execution1 of 5
9
9
4
6
6
8
2
1
cell
1
Begin DFS at value 1 with a one-cell path.
1
dfs(cell) returns memo when known2
start best at 13
for each four-direction neighbor4
if neighbor value is larger5
best = max(best, 1 + dfs(neighbor))6
memoize and return the maximum over startsstart = bottom middle 1best = 1
Truth to preserve / Cost target
Truth to preserve
memo[cell] is the exact longest increasing path beginning at that cell
Cost target
O(rows times cols) time and space
Directed moves to larger neighbors cannot form a cycle. Memoized DFS computes the best path starting at each cell once, then reuses it from every smaller neighbor.
Your call · What should guide every step of this algorithm?