Given an m×n grid of non-negative weights, find the minimum sum along any path from the top-left to the bottom-right moving only right or down.
Example grid: [[1,3,1],[1,5,1],[4,2,1]] → 7.
TimeO(m×n)fill table
SpaceO(m×n)DP table
Current: —Result: —
Grid weight
Min sum so far
Current cell
dp[i][j]
—
Ready
Press Play. dp[i][j] = minimum path sum to (i,j). First cell = grid[0][0]; edge cells = sum along edge; interior = grid[i][j] + min(up, left).
TimeO(m×n)memoized
SpaceO(m×n)memo + call stack
Recursive: dfs(i,j) — base (0,0) returns grid[0][0]; else grid[i][j] + min(dfs(i-1,j), dfs(i,j-1)) with memo. Same DAG as iterative tabulation.
✎ Whiteboard
3
⌨ Type It
Practice until you don't need to look. The green highlights are the nuances to burn into memory.