Example 1
ready- Input
cost = [ 10, 15, 20 ]- Expected
15- Why
- start at stair 1, pay 15, then jump to the top
Min Cost Climbing Stairs
25 min · minCostClimbingStairs()The cheapest-looking first step can lead straight into an expensive staircase.
The array cost records what you pay when you step off each stair: leaving stair
i costs cost[i]. You may begin on stair 0 or stair 1, then climb 1 or 2 stairs
per move. Return the smallest total cost that gets you to the top, just past the final
stair.
A few ground rules:
- Starting on stair 0 or 1 costs nothing by itself; you pay when you leave that stair.
- A final 1-step or 2-step move may land directly on the top.
- Costs are never negative.
Constraints
2 <= cost.length <= 1_0000 <= cost[i] <= 999
Hints
Price each arrival
Ask for the cheapest total that has paid for stair i. The previous move came
from either i - 1 or i - 2.
The top has two entrances
You can reach the top by stepping off either of the final two stairs. Compute the cheapest paid total for both, then take the smaller one.
Two totals are enough
Each new total depends only on the previous two. Roll those values forward instead of storing a full array.
Follow-up
How would you return the actual sequence of stair indices on a cheapest route, not just its cost?
Visible cases
Examples
Example 2
ready- Input
cost = [ 1, 100, 1, 1, 1, 100, 1, 1, 100, 1 ]- Expected
6- Why
- small local costs combine into a six-cost route
Example 3
ready- Input
cost = [ 5, 1 ]- Expected
1- Why
- start at stair 1 and leave it directly for the top
Interview signal
Asked at
AmazonGoogle
Explore every route
Try both legal starting stairs. From stair i, pay cost[i], then recursively try a
1-step move and a 2-step move. Landing at position len(cost) reaches the top; moving
past it isn't a valid route.
def min_cost_climbing_stairs(cost: list[int]) -> int:
def spend_from(i: int) -> int:
if i == len(cost):
return 0
if i > len(cost):
return float("inf")
return cost[i] + min(spend_from(i + 1), spend_from(i + 2))
return min(spend_from(0), spend_from(1))The two branches repeatedly solve the same suffix. The work grows far faster than the input.
Time O(2ⁿ). Space O(n) for the recursion stack.
Rolling minimum DP
Dynamic programming (DP) means keeping answers to overlapping smaller problems. This problem's DP has a precise shape:
- State:
dp[i]is the minimum total after paying the cost of stairi. - Transition:
dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]), because those are the only two stairs that can lead toi. - Base case:
dp[0] = cost[0]anddp[1] = cost[1], since you may start at either stair.
The answer is min(dp[n - 1], dp[n - 2]): either of the final two stairs can launch
the last move to the top. The transition reads only two previous states, so roll them
forward.
def min_cost_climbing_stairs(cost: list[int]) -> int:
two_stairs_back = cost[0]
one_stair_back = cost[1]
for i in range(2, len(cost)):
current = cost[i] + min(one_stair_back, two_stairs_back)
two_stairs_back = one_stair_back
one_stair_back = current
return min(one_stair_back, two_stairs_back)At every iteration, the two variables are exactly the two states named by the transition. Earlier values can't affect another decision.
Time O(n). Space O(1).
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
15
Run: visible + custom · Submit: full suite