Min Cost Climbing Stairs
Min Cost Climbing Stairs: pay cost[i] to leave step i, moving one or two steps at a time; reach past the top for the least total cost.
- 2 <= cost.length <= 1000
- 0 <= cost[i] <= 999
Intuition
Min cost climbing stairs finds the cheapest way to reach the top, where each step charges a cost when stepped on and you may climb one or two steps at a time. Starting is free from either index 0 or index 1.
The recurrence is short, but the definition of the state is where most errors originate:
- dp[i] is the minimum cost to reach step i, not the cost of standing on it — arriving is free until you step off.
With that reading, dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). Each option pays the cost of the step being departed from, not the one arrived at.
Defining the state as "cost including standing on step i" also works but shifts every term by one, and mixing the two conventions mid-solution is the usual source of off-by-one answers.
The base cases follow directly: dp[0] = 0 and dp[1] = 0, since starting at either is free.
The top is one position past the last step, at index n. That is the answer, and returning dp[n-1] instead is the single most common mistake — it stops one step short and omits the final climb.
Only the previous two values are ever needed, so the array collapses to two rolling variables and O(1) space.
A greedy that always takes the cheaper next step fails, because a cheap step can force an expensive one afterwards. The DP considers both routes to every position, which is what makes it correct.
The cost is paid when you leave a step, not when you land on it, and you may start from either index 0 or 1. Defining dp[i] as the cost to reach step i makes both facts fall out: dp[0] and dp[1] are free, and reaching the top means index n.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n) time and O(n), or O(1) with two rolling variables space.
Define reaching, not standing
dp[i] is the cost to reach step i, and arriving is free — the cost is paid when stepping off. Mixing this with the other convention causes off-by-one answers.
Set both base cases to zero
dp[0] = 0 and dp[1] = 0, since starting from either index is free. No cost is incurred before the first move.
Write the recurrence
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). Each option pays for the step departed from, not the one arrived at.
Return the position past the end
The top is index n, one beyond the last step. Returning dp[n-1] stops one step short — the most common error in this problem.
Collapse to two variables
Only the previous two values are read, so the array reduces to two rolling variables and O(1) space with no logic change.
Reject the greedy
Always taking the cheaper next step fails, since a cheap step can force an expensive one after it. The DP weighs both routes to every position.
Cost of the scan
One pass with constant work per step gives O(n) time and O(1) space.
Solution & live demo
Common pitfalls
Sizing the table to n instead of n + 1
dp = [0] * n return dp[n - 1]
dp = [0] * (n + 1) return dp[n]
The destination is the floor past the last step, not the last step itself. Returning dp[n-1] stops one short and omits the final move's cost.
Adding cost[i] when landing
dp[i] = cost[i] + min(dp[i-1], dp[i-2])
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
You pay for the step you jump from. Charging on arrival double-counts the starting step and never charges the last one, shifting the whole answer.
Forcing a start at index 0
dp[1] = cost[0]
dp[0] = dp[1] = 0
The problem allows starting at either of the first two steps. Charging cost[0] to reach index 1 removes the option of starting there, which is optimal whenever cost[0] is large.
Edge cases
dp[0] = dp[1] = 0, so dp[2] = min(cost[0], cost[1]) -- you pay for exactly one step no matter which you start on.
The min() at each fill step naturally routes around it by hopping two steps instead of landing on it.
Every path costs the same per step taken; the DP still finds the path using the fewest steps, which ties out to the same total.
Doing so stops one step short of the goal and silently pays for a move that was never required -- the goal is always dp[n].