718. Falling Path Minimum
A raindrop falls through a slab of rock modelled by grid, where grid[r][c] is the resistance of that cell (it may be negative for porous cells that help the drop). The drop enters at any cell of the top row. From the cell in column c of row r it moves to row r + 1, landing in column c - 1, c or c + 1, never leaving the slab.
Return the smallest possible total resistance of the cells visited on a fall from the top row to the bottom row.
Aim for time O(rows * cols) and extra space O(cols).
Example 1
- Input:
- grid = [[5,-2,7],[3,4,-8],[6,-1,2]]
- Output:
- -11
- Explanation:
Falling through -2, -8 and then -1 gives -11, the lowest total.
Example 2
- Input:
- grid = [[9],[-4],[6],[1]]
- Output:
- 12
- Explanation:
A one-column slab forces the straight path: 9 - 4 + 6 + 1 = 12.
Constraints
1 ≤ rows, cols ≤ 300
-100 ≤ grid[r][c] ≤ 100
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)