Minimum Path Sum
Medium· grid DP
Problem
Given a grid of non-negative numbers, walk from the top-left to the bottom-right moving only right or down. Return the smallest possible sum of the numbers along the path.
Examples
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
1→3→1→1→1.
Input: grid = [[1,2,3],[4,5,6]]
Output: 12
Constraints
- • 1 <= m, n <= 200
- • 0 <= grid[i][j] <= 200
Hints & approach
Hint 1
Same movement rules as Unique Paths, but minimise instead of count.
Hint 2
The first row and column each have only one way in.
Hint 3
cost[i][j] = grid[i][j] + min(cost[i-1][j], cost[i][j-1]).
Approachtry the hints first
Let cost[i][j] be the cheapest path sum ending at (i, j). The first row and column are running prefix sums since they have a single approach. Every other cell adds its own value to the cheaper of the cell above and the cell to the left. A single row array updated left to right is sufficient, or the grid can be updated in place.
Time O(m·n) · Space O(n)