Problem context and objectives
Mission briefing
Energy-route planner · A runner crosses a line of power stations
Build each decision from smaller outcomes already solved: The Priced Stairs.
Re-solving the same future branches drains exponential energy.
How you win
- 1Recognize when Minimum cost climbing stairs matches the clues
- 2Keep this true after every move: the two rolling states are the cheapest costs to reach the preceding two positions
- 3Reach the result within O(n) time and O(1) space
Rules and pressure
- Target cost: O(n) time and O(1) space
- State rule: the two rolling states are the cheapest costs to reach the preceding two positions
Lesson 1 of 3
Live algorithm trace
Minimum cost climbing stairs
Complete execution1 of 5
Initialize the two legal starting positions with zero paid cost.
1
twoBack = oneBack = 02
for each step position through the top3
costHere = 0 at top, else cost[index]4
current = costHere + min(oneBack, twoBack)5
shift rolling states6
return cost at toptwoBack = 0oneBack = 0
Truth to preserve / Cost target
Truth to preserve
the two rolling states are the cheapest costs to reach the preceding two positions
Cost target
O(n) time and O(1) space
The cheapest arrival at a step comes from one or two steps below. Add the destination step's cost, while the top beyond the array costs nothing.
Your call · What should guide every step of this algorithm?