Given an array cost where cost[i] is the price of stepping on stair i, you may start from step 0 or step 1, and from any step you can climb 1 or 2 steps. Return the minimum total cost to reach the top — one step past the last stair.
Example
Input cost = [10,15,20]
Output 15
Key Pointers
"Top" means one step past the last index — you don't have to land on the final stair, just get past it.
minCost(i) = cost[i] + min(minCost(i-1), minCost(i-2)) — the price of a step plus whichever of the two prior steps was cheaper to arrive from.
Like Climbing Stairs, only the last two computed costs are ever needed at a time.
Step-by-Step Analysis
Initialize two running values: two_back = cost[0], one_back = cost[1].
For each index i from 2 to the last index, compute current = cost[i] + min(one_back, two_back), then shift both values forward.
After the loop, the answer is min(one_back, two_back) — the cheaper of the last two stairs, since the top is reachable from either.
Complexity
Time: O(n) — Space: O(1)
Code
def minCostClimbingStairs(cost: list[int]) -> int:
two_back, one_back = cost[0], cost[1]
for i in range(2, len(cost)):
two_back, one_back = one_back, cost[i] + min(one_back, two_back)
return min(one_back, two_back)
Code Explanation
How the solution above works, piece by piece.
Let best(i) = the cheapest total cost of standing on step i (you pay cost[i] when you step on it). Steps 0 and 1 are free starting points, so best(0) = cost[0], best(1) = cost[1].
Step i is reached from i − 1 or i − 2: best(i) = cost[i] + min(best(i−1), best(i−2)).
Only the last two values are needed, so two variables replace a table; the tuple assignment shifts them each loop.
The top is past the last step and can be reached from either of the last two steps, so return min(one_back, two_back).
O(n) time, O(1) space.
Visual Walkthrough
Running it on cost = [10, 15, 20]:
Stepping on step 2 would cost 20 + 10 = 30. Jumping from step 1 (cost 15) straight past the end is cheaper, so the answer is 15.