Minimum Path Sum
Given an m x n grid filled with non-negative numbers, find a path from the top-left corner to the bottom-right corner that minimizes the sum of all numbers along the path.
You may only move either down or right at any point in time.
Return the minimum possible path sum.
Example 1
1 3 1 1 5 1 4 2 1
Input
grid = [[1,3,1],[1,5,1],[4,2,1]]Output
7The path 1 → 3 → 1 → 1 → 1 has the minimum sum of 7.
Example 2
1 2 3 4 5 6
Input
grid = [[1,2,3],[4,5,6]]Output
12The path 1 → 2 → 3 has the minimum sum of 6.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 200
- 0 <= grid[i][j] <= 200