Minimum Path Sum
Minimum Path Sum
Given a grid of non-negative numbers, find a path from top-left to bottom-right minimizing the sum. You may move only right or down.
Why this is worth learning
The set of predecessors is identical to path counting, but the aggregation changes: choose the cheaper predecessor, then pay for the current cell exactly once.
Before coding: one-minute experiment
For [[1,3,1],[1,5,1],[4,2,1]], what is the minimum path sum and which path achieves it?
Function signature
func MinPathSum(grid [][]int) int
Inputs / outputs
grid: non-negative costs.- Return: minimum path sum.
Example
1 3 1
1 5 1
4 2 1
Minimum path: 1->3->1->1->1 = 7
Output: 7
Constraints
- 1 <= m, n <= 200
- The grid is rectangular and its cell values are nonnegative.
- For every cell, the minimum path sum from the top-left corner to that cell is guaranteed to fit the target Go
int.
Core idea (near-solution)
DP where each cell cost is its value plus the minimum of top/left paths.
Invariant: before updating an interior column c>0, dp[c] still stores the previous row’s minimum prefix costs from above, while dp[c-1] already stores the current row’s value from the left. After the write, dp[c] has the current cell’s answer.
Algorithm (step-by-step)
- Initialize dp for the first row with cumulative sums.
- For each next row:
- Update dp[0] by adding grid[r][0].
- For c=1..n-1, dp[c] = min(dp[c], dp[c-1]) + grid[r][c].
- Return dp[n-1].
Correctness sketch
Every path ending at (r,c) has a last predecessor above or to the left. Its cost equals that predecessor path cost plus grid[r][c]. Replacing the prefix by a cheaper path to the same predecessor preserves feasibility, so the optimum is the cell value plus the minimum optimal predecessor cost. Initialize the first row and first column by their unique paths. The rolled array keeps old-row costs above and already-updated current-row costs left, so each update implements the recurrence. The final entry is the minimum cost including both start and destination.
Trace (hand walkthrough)
Example input:
1 3 1
1 5 1
4 2 1
Minimum path: 1->3->1->1->1 = 7
Output: 7
Walk:
- dp row0: [1,4,5]
- dp row1: [2,7,6]
- dp row2: [6,8,7] -> min sum 7
Pitfalls to avoid
- Forgetting to initialize the first row/column correctly.
- Using max instead of min.
Debugging lens
Test a single cell, one row, one column, and a locally cheap first move that is globally worse. Preserve the input grid and keep every intermediate sum representable.
Complexity
- Time:
O(m*n). - Extra space:
O(n).
Implementation notes (Go)
- Use a 1D dp slice to save space.
Contract precision
The grid is read-only. The representability guarantee applies to every prefix-cell minimum, including cells outside the final cheapest path; a representable destination minimum alone is not sufficient for this recurrence. The function has no checked-overflow result.
Reconstruction checkpoint
For [[1,3,1],[1,5,1],[4,2,1]], what is the minimum path sum and which path achieves it?
Model answer
The minimum is 7 along values 1,3,1,1,1: move right, right, down, down. The start and destination are each included once.