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.

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

Core idea (near-solution)

DP where each cell cost is its value plus the minimum of top/left paths.

Invariant: dp[c] is the minimum sum to reach column c in the current row.

Algorithm (step-by-step)

1. Initialize dp for the first row with cumulative sums.
2. 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].
3. Return dp[n-1].

Correctness sketch

• Invariant: dp[c] is the minimum sum to reach column c in the current row.
• The DP state represents the optimal answer for a prefix or subproblem.
• The recurrence uses only previously solved states, preserving correctness.
• The final DP value (or max over DP) is the correct answer.

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.

Complexity

• Time: O(m*n).
• Extra space: O(n).

Implementation notes (Go)

• Use a 1D dp slice to save space.