FunctionRacerProblemsRace

Two-Lane Road

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

A road is split into segments, and it has a left lane and a right lane. Driving segment i costs left[i] in the left lane and right[i] in the right lane. You may start in either lane, and between two segments you may move to the other lane, which costs change each time.

Return the smallest total cost of driving every segment, in order. An empty road costs 0.

Example 1

left [1,9,1,9]
right [9,1,9,1]
change 3
returns 13

Start left and change lanes before each later segment: 1 + 3 + 1 + 3 + 1 + 3 + 1 = 13.

Example 2

left [1,9,1,9]
right [9,1,9,1]
change 10
returns 20

Changing now costs 10, so staying in one lane the whole way, for 20, is cheapest.

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