FunctionRacerProblemsRace

Cheapest Toll Route

EasyDynamic programmingPython, JavaScript, TypeScript, Java, C++

Every cell of the grid tolls holds the toll you pay when you enter it. You start in the top left cell (paying its toll as well) and want to reach the bottom right cell, moving only one cell right or one cell down at a time. Return the smallest total toll you can pay on the way, counting the start cell and the end cell. A grid with a single cell costs just that cell's toll.

Example 1

tolls [[1,3,1],[1,5,1],[4,2,1]]
returns 7

The cheapest route goes right, right, down, down and pays 1 + 3 + 1 + 1 + 1 = 7.

Example 2

tolls [[2,9],[1,3]]
returns 6

Going down first pays 2 + 1 + 3 = 6, while going right first would pay 2 + 9 + 3 = 14.

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