Toll Road With Long Jumps
Problem
A road is divided into n cells. Landing on cell i changes your balance by tolls[i] coins paid (a negative toll is a rebate). You start on cell 0, paying its toll, and must finish exactly on cell n - 1, paying its toll too.
From cell i you may jump forward to any cell i + 1 … i + k. Return the minimum total toll for the trip.
Example 1
- Input:
- tolls = [1, -3, 4, 2, -1, 5], k = 2
- Output:
- 4
Cells 0, 1, 3, 4, 5: 1 - 3 + 2 - 1 + 5 = 4.
Example 2
- Input:
- tolls = [2, 9, 9, 9, 1], k = 3
- Output:
- 12
Cells 0, 3, 4 or 0, 1, 4: 2 + 9 + 1 = 12. A jump of 4 is too long.
Constraints
- 1 ≤ tolls.length ≤ 10^5
- 1 ≤ k ≤ 10^5
- -10^4 ≤ tolls[i] ≤ 10^4
Hint
Show the first hint
Define cost(i) = cheapest total to stand on cell i. Which cells can you have come from?
Walkthrough
How to approach it
01Clarify before coding
- Are both the first and last tolls paid? Yes, every landed cell counts, including start and finish.
- Can tolls be negative? Yes, so you may want to land on many cells; you still may only move forward.
- Can k exceed n? Yes; then any cell can jump straight to the end.
02Brute force
The straightforward DP: cost(i) = tolls[i] + min over the k previous cells, scanning them every time. Plain recursion from cell 0 trying all k jumps is exponential before memoisation.
Cost: O(n·k) time: 10^10 operations when n = k = 10^5. Correct, but too slow.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.