Minimum cost to climb
Same bottom-up array, but the recurrence takes the smaller of two costs instead of adding two counts. About 10 minutes.
Every stair has a toll
Now each stair has a price. Stepping off a stair costs its toll, and from there you move up 1 or 2 stairs. You may start on the first or the second stair for free. What's the cheapest way to get past the top?
Same trick again: think about how you arrived. To stand on a stair, you came from the stair just below (and paid its toll) or from two below (and paid that one's toll). You'd pick whichever total is cheaper.
You may start on stair 0 or stair 1 for free, so standing on either costs nothing.
The finish line is past the last stair
A small trap: "the top" isn't the last stair, it's the landing just above it. With 3 stairs you're done when you reach position 3, which isn't a stair at all and has no toll.
So the table has one more box than there are stairs, and that last box holds the answer. With tolls 10, 15 and 20, the cheapest route starts on the 15 and jumps two stairs straight onto the landing: 15 in total.
n = len(cost)
# standing on stair 0 or 1 is free
best = [0] * (n + 1)
for i in range(2, n + 1):
best[i] = min(best[i - 1] + cost[i - 1],
best[i - 2] + cost[i - 2])
return best[n]The cheapest way to reach stair 2 costs 3, and leaving stair 2 costs 4. What does it cost to reach stair 4 by jumping from stair 2?
- A7
- B3
- C4
Show the answer
7. 3 to get to stair 2, plus the toll of 4 to leave it: 7.
Minimum cost to climb
cost[i] is the cost to leave step i, for a staircase with steps 0 to n-1 (n = cost.length). From any step you can move up by 1 or by 2, and you may start at step 0 or step 1 for free. Return the minimum total cost to reach the top, one step past the last one (index n).
cost = [10, 15, 20] → 15
2 ≤ cost.length ≤ 1,000 · 0 ≤ cost[i] ≤ 1,000