Problem Statement
Min Cost Climbing Stairs
You have a staircase. The array cost tells you how much you pay to stand on each step, so cost[i] is the price of step number i. Once you pay for a step, you can move up by one step or by two steps. You may begin at step 0 or at step 1. Your goal is to reach the top, which is the spot just past the last step, for the smallest total price possible. Return that smallest total.
Signals to notice
Brute force first
Try every combination of 1-step and 2-step moves. Each position branches into two choices. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.
The key insight
DP: dp[i] = cost[i] + min(dp[i-1], dp[i-2]). The cost to reach step i is its own cost plus the cheaper of the two steps that could reach it. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.
Trace it on cost=[1,100,1,1,1,100,1,1,100,1]
init: prev2=cost[0]=1, prev1=cost[1]=100 i=2: curr=1+min(100,1)=2 -> prev2=100, prev1=2 i=3: curr=1+min(2,100)=3 -> prev2=2, prev1=3 i=4: curr=1+min(3,2)=3 -> prev2=3, prev1=3 i=5: curr=100+min(3,3)=103 -> prev2=3, prev1=103 i=6..8: prev1 becomes 4,5,104 -> prev2=5, prev1=104 i=9: curr=1+min(104,5)=6 -> prev2=104, prev1=6 return min(prev1,prev2)=min(6,104)=6
What must stay true
At each step, you arrived from either i-1 or i-2 — take the cheaper one. This greedy-like choice is valid because there are no future consequences beyond the immediate cost. As long as that statement keeps holding, you can trust the steps built on top of it.
Shape of the loop
prev2, prev1 = cost[0], cost[1]
for i from 2 to n-1:
curr = cost[i] + min(prev1, prev2)
prev2, prev1 = prev1, curr
return min(prev1, prev2)Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Confusing where you start and end — you can start from index 0 OR 1, and the top is one step past the last index. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.