Minimum Path Sum
MediumDynamic Programming · NVIDIA
You are given an m x n grid of non-negative integers. Start at the top-left cell grid[0][0] and travel to the bottom-right cell grid[m - 1][n - 1], moving only right or down one cell at a time.
The cost of a path is the sum of every cell it visits, including the start and end cells. Return the minimum possible cost.
Example 1
- Input:
- grid = [[1, 4, 2, 1], [3, 1, 1, 5], [6, 7, 2, 1]]
- Output:
- 9
- Explanation
- Go down to 3, right to 1, right to 1, down to 2, then right to 1. The cost is 1 + 3 + 1 + 1 + 2 + 1 = 9.
Example 2
- Input:
- grid = [[9], [1], [1]]
- Output:
- 11
- Explanation
- With a single column the only path goes straight down: 9 + 1 + 1 = 11.
Example 3
- Input:
- grid = [[0, 5], [7, 0]]
- Output:
- 5
- Explanation
- Both paths include the two 0 corners. Going right first adds 5 and going down first adds 7, so the answer is 5.
Constraints
m == grid.length,n == grid[i].length- 1 ≤
m,n≤ 200 - 0 ≤
grid[i][j]≤ 200