714. Lightest Grid Path
A delivery drone flies over a city block map grid, where grid[r][c] is the fuel burned when crossing that cell. The drone starts in the top-left cell and must land in the bottom-right cell. Every move goes one cell right or one cell down.
The fuel used by a flight is the sum of the values of all cells it visits, including the first and the last one. Return the smallest possible fuel total.
Aim for time O(rows * cols) and extra space O(cols).
Example 1
- Input:
- grid = [[4,1,6],[2,9,3],[5,1,2]]
- Output:
- 14
- Explanation:
Going down, down, right, right visits 4, 2, 5, 1, 2 for a total of 14, which beats every other route.
Example 2
- Input:
- grid = [[8,0,5,3]]
- Output:
- 16
- Explanation:
A single row leaves only one route, so the cost is 8 + 0 + 5 + 3 = 16.
Constraints
1 ≤ rows, cols ≤ 300
0 ≤ grid[r][c] ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(rows * cols)
- Space
- O(cols)