Minimum Path Sum
Easy
Given a m x n grid filled with non-negative integers, find a path from the top-left corner to the bottom-right corner that minimizes the sum of all numbers along its path.
You can only move:
- Right
- Down
Return the minimum path sum.
Example 1
Input
m = 3
n = 3
grid =
[
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
]Output
7
Explanation
The minimum path is:
1 → 3 → 1 → 1 → 1
Therefore:
1 + 3 + 1 + 1 + 1 = 7
Example 2
Input
m = 2
n = 3
grid =
[
[1, 2, 3],
[4, 5, 6]
]Output
12
Explanation
The minimum path is:
1 → 2 → 3 → 6
Therefore:
1 + 2 + 3 + 6 = 12
Constraints
1 <= m
n <= 200
0 <= grid[i][j] <= 200
You can only move right or down.
Hints:
Hint 1
For each cell, the minimum path to reach it comes from either:
- The cell above
- The cell to the left
Hint 2
Use:
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
Auto
Loading editor...
Input
Expected Output