Jump Game with Fee
Medium · Dynamic Programming · Array · Dynamic Programming
Problem
A staircase has n steps numbered 0 to n - 1, and fee[i] is the fee charged for leaving step i. You stand on step 0 and want to get past the top: any position n or beyond.
From step i you may move up 1, 2 or 3 steps, and that move costs fee[i], the fee of the step you leave. Nothing is charged on arrival.
Return the minimum total fee needed to get past the last step.
Examples
Input: fee = [1,2,5,2,1,2] Output: 3
Jump from step 0 to step 3 (pay 1), then from step 3 past the top (pay 2).
Input: fee = [2,3,4,5] Output: 5
Move from step 0 to step 1 (pay 2), then jump three steps from step 1, past the top (pay 3).
Input: fee = [4] Output: 4
You must leave step 0 once, which costs 4.
Constraints
- 1 <= len(fee) <= 10^4
- 0 <= fee[i] <= 1000
Approaches
- Baseline: shortest path with a heap — time O(n log n), space O(n)
Follow-up
What if the fee is paid where you land and you must stop exactly on the last step, or you need the number of cheapest routes rather than their cost? See the use cases “Pay where you land, stop on the last step” and “How many cheapest routes”.
Related problems
Start free on Cariara · Coding problems · System design studio
