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 Weighted Matrix.
A greedy step can trap the robot; recomputing every route is too expensive.
How you win
- 1Recognize when Minimum path sum matches the clues
- 2Keep this true after every move: dp[col] is the cheapest cost to the current row and column
- 3Reach the result within O(rows times cols) time and O(cols) space
Rules and pressure
- Target cost: O(rows times cols) time and O(cols) space
- State rule: dp[col] is the cheapest cost to the current row and column
Lesson 1 of 3
Live algorithm trace
Minimum path sum
Complete execution1 of 6
1
cell
3
1
1
5
1
4
2
1
Place a zero-cost virtual parent before the start.
1
initialize dp with infinity2
dp[0] = 03
scan each grid cell4
bestParent = min(top, left)5
dp[col] = bestParent + grid cell6
return dp[last]dp = [0,inf,inf]
Truth to preserve / Cost target
Truth to preserve
dp[col] is the cheapest cost to the current row and column
Cost target
O(rows times cols) time and O(cols) space
Every cell pays its own cost plus the cheaper of the best route from above or left. One row of state is enough.
Your call · What should guide every step of this algorithm?