Least Charge to Cross
A robot crosses a grid of rooms from the top left room to the bottom right room, moving only right or down. Entering a room adds rooms[r][c] to its battery charge; a negative value drains it. This also happens in the first room and in the last one.
The charge must be at least 1 at every moment, from before the first room until after the last. Return the least charge the robot can start with.
Example 1
rooms [[-3,5],[2,-6]]
returns 5
Go right, then down. Starting with 5 the charge runs 2, 7, 1. The other way passes -3, 2 and -6 and needs 8.
Example 2
rooms [[4]]
returns 1
The room only adds charge, but the robot still needs 1 to start.
Constraints
1 <= len(rooms) <= 201 <= len(rooms[0]) <= 20, and every row has that length-1000 <= rooms[r][c] <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Patterns With Repeat MarksHard
- Shatter the CrystalsHard
- Two Pickers Down the FieldHard
- Two Towers of One HeightHard
- Factorials Up to nBeginner
- Fibonacci NumberBeginner
- Frog Across the StonesBeginner
- Hop One or ThreeBeginner