Description
Each stair has a nonnegative cost paid when stepping on it. Start at index 0 or 1, then climb one or two stairs per move. Find the minimum cost to reach just beyond the last stair; assume at least two stairs.
Solution
def min_cost_climbing_stairs(cost):
previous, current = 0, 0
for i in range(2, len(cost) + 1):
previous, current = current, min(current + cost[i - 1], previous + cost[i - 2])
return currentExamples
Example 1
- Input
[[10,15,20]]- Output
15
Start at stair 1 and jump to the top.
Example 2
- Input
[[1,100,1,1,1,100,1,1,100,1]]- Output
6
Avoid the expensive stairs.
Example 3
- Input
[[0,0]]- Output
0
Both starting choices are free.
Approach
Let the cost to reach position i be the minimum of reaching i - 1 and paying that stair, or reaching i - 2 and paying that stair. Keep only those two previous values.
Time & space
O(n) time and O(1) auxiliary space, where n is stair count.