Cheapest Stair Climb
Problem
A staircase charges a toll for stepping on each stair, given as a list where position i holds the toll for stair i. From any stair you may move up one or two stairs, and you may begin from either stair 0 or stair 1 without paying to arrive there. Return the cheapest total toll for reaching the floor just past the last stair.
Examples
Input: cost = [10, 15, 20]
Output: 15
Why: start on stair 1, pay 15, then jump two stairs to the topInput: cost = [1, 100, 1, 1, 100, 1]
Output: 4
Why: stepping only on the cheap stairs costs four in totalInput: cost = [5, 3]
Output: 3
Why: edge case, starting on the cheaper stair and jumping straight offHints
0 / 3
The cheapest way to stand somewhere depends only on the cheapest ways to stand at the two places you could have come from.
Work upward from the bottom instead of guessing a route from the top, and give the two starting stairs a cost of nothing.
For each position in turn, take the smaller of arriving from one stair below or two stairs below, adding that stair own toll. Since only the two previous results are ever needed, keep them in two variables instead of a whole table.
Solution
Reaching any position is only possible from one or two stairs below, so its cheapest cost is the smaller of those two costs plus the toll of the stair being left. Both starting stairs cost nothing to stand on, which seeds the recurrence. Because each step looks back at most two positions, two rolling variables replace the full table. Time is O(n) and space is O(1).
def cheapest_climb(cost):
back2, back1 = 0, 0 # cheapest cost of the two positions behind
for i in range(2, len(cost) + 1):
# arrive from one stair below or two, paying that stair own toll
current = min(back1 + cost[i - 1], back2 + cost[i - 2])
back2, back1 = back1, current
return back1
print(cheapest_climb([10, 15, 20])) # -> 15
print(cheapest_climb([1, 100, 1, 1, 100, 1])) # -> 4
print(cheapest_climb([5, 3])) # -> 3Stuck on the idea rather than the code? Climbing Stairs covers it.