Min Cost Climbing Stairs
The gentlest optimisation DP — the same recurrence as climbing stairs, but choosing a minimum instead of counting
Problem Statement
Each index of cost holds the price of stepping off that stair. You may climb one or two stairs at a time, and you may start at index 0 or index 1. Return the cheapest way to get past the top.
Input: cost = [10, 15, 20]
Output: 15
start at index 1, pay 15, jump two → done
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
pay 1 at indices 0, 2, 4, 6, 7, 9Intuition
The recursive statement is easy: to stand past the top you must have left either the last stair or the second-to-last. To reach those, the same question applies one step earlier.
Written directly, that recursion recomputes the same stairs from both branches — the identical waste shown on the dynamic programming page.
The insight
Ask "what is the cheapest way to arrive at each stair?" rather than "where should I step next?"
You can only reach stair i from i - 1 or i - 2. So:
min_cost(i) = cost[i] + min( min_cost(i-1), min_cost(i-2) )
└ pay to └ arrive as cheaply as possible
leave iBoth are smaller subproblems already answered. Work forwards and each is one lookup.
This is Climbing Stairs with + swapped for min. Counting becomes optimising and nothing else changes — a substitution worth noticing, because it recurs across most of DP.
Where the answer lives
The top is past the last stair. You can reach it from the last stair or the second-to-last, so the answer is min(dp[n-1], dp[n-2]) — not simply the final cell.
Approach
Base cases: the first two stairs cost only themselves
You may start at either, so arriving there is free beyond their own price.
The answer is the cheaper of the final two
The top is beyond the array, reachable from either.
Solution
def min_cost_climbing_stairs(cost: list[int]) -> int:
"""Cheapest way to climb past the top of the staircase.
Only the previous two values are ever needed, so two variables
replace the table entirely.
"""
prev2, prev1 = cost[0], cost[1]
for i in range(2, len(cost)):
prev2, prev1 = prev1, cost[i] + min(prev1, prev2)
return min(prev1, prev2)The tuple assignment updates both at once. Written as two separate statements, prev2 is overwritten before it is read — a bug that produces plausible-looking wrong answers.
The full table version, for comparison
dp[0], dp[1] = cost[0], cost[1]
for i in 2..n-1:
dp[i] = cost[i] + min(dp[i-1], dp[i-2])
return min(dp[n-1], dp[n-2])Identical logic, O(n) memory instead of O(1). Write this first if the two-variable version feels like a trick — then notice only the last two entries are ever read, and collapse it.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Time — one pass, one comparison and one addition per stair.
Space — two variables. The table collapses because the recurrence never looks back further than two steps.
Edge Cases
Related Problems
- Climbing Stairs — the same recurrence, counting instead of minimising
- House Robber — another two-variable DP where the choice is skip or take
- Coin Change — minimising when greedy definitively fails