Minimum Path Sum
Implement minPathSum
Given a grid where every cell holds a non-negative cost, and starting at the top-left corner with only right and down moves allowed, find the minimum possible total cost of any path to the bottom-right corner — the sum of every cell's cost along the way, including both endpoints.
Every cell's cheapest total is its own cost plus whichever of the two cells that could lead into it — the one above, or the one to its left — offers the cheaper cost so far. The very first row and first column each only have one possible way in (straight along the edge), so their running totals are just a simple accumulation of costs with no comparison needed. Filling in the grid this way, one row at a time, means every cell's cheapest cost is already known by the time a later cell needs to compare against it, and the bottom-right corner ends up holding the answer.
Example 1:
Input: grid = [[2,4,1],[5,3,2],[1,6,3]]
Output: 12
Example 2:
Input: grid = [[5,2],[7,3]]
Output: 10
Example 3:
Input: grid = [[9]]
Output: 9
+ 7 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ grid.length, grid[0].length ≤ 50 - ●
0 ≤ grid[i][j] ≤ 100
grid =
[[2,4,1], [5,3,2], [1,6,3]]