Min Cost Climbing Stairs
Find the cheapest way to the top of a staircase where each step has a cost, with a one-line DP over the two ways into every step.
Problem Understanding
Min Cost Climbing Stairs: cost[i] is what you pay to step off stair i, after which you climb one or two stairs. You may start on stair 0 or stair 1. Return the minimum cost to reach the top, which is just past the last stair.
Example: cost = [10, 15, 20] returns 15: start on stair 1, pay 15, and climb two to the top.
The Intuition: Two Ways Into Every Step
Like Climbing Stairs, you can only arrive at step i from i − 1 or i − 2. The difference is that each way has a price, so instead of counting ways, keep the cheapest.
Let dp[i] be the cheapest total to stand on step i, with the top as step n:
dp[0] = dp[1] = 0(free start).dp[i] = min(dp[i − 1] + cost[i − 1], dp[i − 2] + cost[i − 2]).
The answer is dp[n]. Each step depends on the two before it, just like House Robber, so two variables are enough if you want O(1) space.
Interactive Walkthrough
The costs and the dp row line up by step; dp has one extra cell for the top. At each step, the cheaper way in is shaded: the step it climbs from and the cost paid to leave it.
Dry Run Table
Input: cost = [10, 15, 20]
| i | from i−1 | from i−2 | dp[i] |
|---|---|---|---|
| 0 | — | — | 0 |
| 1 | — | — | 0 |
| 2 | 0 + 15 = 15 | 0 + 10 = 10 | 10 |
| 3 (top) | 10 + 20 = 30 | 0 + 15 = 15 | 15 |
The Solution Template
Bottom-up DP with the top as step n.
Min Cost Climbing Stairs Code
1var minCostClimbingStairs = function(cost) {2 const n = cost.length;3 const dp = new Array(n + 1).fill(0);4 for (let i = 2; i <= n; i++) {5 dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);6 }7 return dp[n];8};
Edge Cases & Common Mistakes
- Returning dp[n − 1]: the top is past the last stair; the answer is
dp[n]. - Charging for the start: starting on step 0 or 1 is free, so both base cases are 0, not
cost[0]andcost[1]. - Two stairs:
[5, 3]gives3: start on stair 1 and climb once. - Paying on arrival instead of departure: the cost belongs to the step you leave, so
dp[i]addscost[i − 1]orcost[i − 2].
Summary
dp[i] is the cheapest total to stand on step i, with the top as step n and free starts at 0 and 1. Each step takes the cheaper of climbing from i − 1 or i − 2, paying the cost of the step left. Return dp[n]. O(n) time; O(1) space with two variables.
More practice: DSA interview questions with answers · patterns cheat sheet