FunctionRacerProblemsRace

Least Charge to Cross

HardDynamic programmingPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems