Minimum Path Sum

Problem Given an m x n grid of non-negative numbers, find the minimum path sum from top-left to bottom-right moving only right or down.

Input / Output

• Input: int grid[m][n]. Output: minimum path sum.

Constraints

• 1 <= m, n <= 200; O(m*n) DP.

Example

• [[1,3,1],[1,5,1],[4,2,1]] → 7 (1→3→1→1→1).

Expected approach

• DP: dp[i][j] = grid[i][j] + min(dp[i−1][j], dp[i][j−1]); first row/column accumulate. O(m*n) time; O(n) rolling row, or in-place on the grid if mutation is allowed (ask first). Path reconstruction by walking back through the min-choices is the common follow-on; know why plain greedy (always take the smaller neighbor) fails.