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: Paths Across the Matrix.
A greedy step can trap the robot; recomputing every route is too expensive.
How you win
- 1Recognize when Grid dynamic programming matches the clues
- 2Keep this true after every move: each processed cell stores all paths that reach it
- 3Reach the result within O(rows × cols)
Rules and pressure
- Target cost: O(rows × cols)
- State rule: each processed cell stores all paths that reach it
Lesson 1 of 3
Live algorithm trace
Grid dynamic programming
Complete execution1 of 5
1
cell
1
1
1
1
1
The top row has exactly one right-only path to each cell.
1
dp = [1] * cols2
for each remaining row3
dp[col] += dp[col-1]4
return dp[-1]rows = 2cols = 3dp = [1, 1, 1]
Truth to preserve / Cost target
Truth to preserve
each processed cell stores all paths that reach it
Cost target
O(rows × cols)
A grid state counts ways to reach one cell. With only right and down moves, every arrival comes from above or left.
Your call · What should guide every step of this algorithm?