Two-Lane Road
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
0 <= len(left) <= 100len(right) == len(left)0 <= left[i], right[i] <= 10000 <= change <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Best Stretch SumMedium
- Cheapest DescentMedium
- Cheapest Pool PassesMedium
- Coins From Either EndMedium
- Count DerangementsMedium
- Count the Free PlotsMedium
- Dice Sum WaysMedium
- Fairest Stone SplitMedium