A delivery robot crosses a warehouse grid grid from the top-left cell to the bottom-right cell, moving only right or down. Each cell charges (positive number) or drains (negative number) its battery by that amount when the robot enters it, including the first and last cells. The battery level must be at least 1 at every moment, and it has no upper limit. Return the smallest starting battery level that lets the robot finish along some route.
Examples
Input: grid = [[-3, 5],
[-10, 2]]
Output: 4
Explanation: go right then down: 4 -> 1 -> 6 -> 8.
Input: grid = [[0]]
Output: 1
Constraints
1 <= rows, cols <= 100-1000 <= grid[i][j] <= 1000- Target complexity: O(rows * cols).
Goals
- Recognise when a forward DP cannot capture the constraint and work backwards instead
- Clamp the required amount so it never falls below the minimum