core practice · coding problem
Minimum path sum in a grid
Grid [[1,3,1],[1,5,1],[4,2,1]]. Min path sum top-left to bottom-right moving only right/down?
The mechanism
2D dynamic programming fills a table where each cell depends on a few neighbors (often the ones above and to the left). The hard part is naming the state precisely — once dp[i][j] has a clear one-sentence meaning, the recurrence usually falls out.
Expected evidence
7 via 1→3→1→1→1.
Try this drill in the practice workspace →
Hints when you need them
- dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1]).
- Can roll to 1D array.