Min Cost Climbing Stairs
Problem
0..n-1, and stepping off step i costs
cost[i]. After paying, you may climb one or two steps. You may start on
step 0 or step 1 for free. Return the minimum total cost to
reach the top, which is the position just past the last step (index n).cost = [10,15,20]Output15cost = [1,100,1,1,1,100,1,1,100,1]Output62 ≤ n ≤ 1000 · 0 ≤ cost[i] ≤ 999
Try it yourself
class Solution {
public int minCostClimbingStairs(int[] cost) {
}
}
reach(i) be the cheapest way to stand on position
i. You arrive from i-1 or i-2, paying that step's cost:
reach(i) = min(reach(i-1)+cost[i-1], reach(i-2)+cost[i-2]). Only the last two
values matter.Instinct The best answer at position i depends only on a few earlier positions (i-1, i-2, ...) - write dp[i] from its predecessors, then roll it into variables.
Memory hack Look back, pick best, roll forward - every step only remembers the last couple of stairs it stood on.
Open the 1-D Dynamic Programming guide →Approaches
Brute ForcePlain Recursion
O(2n)Space O(n)Translate the recurrence directly: to reach position i, try both
possible previous positions and keep the cheaper total. Positions 0 and
1 are free starting points. The same sub-positions are recomputed over and
over, so the call tree doubles at every level.
public int minCostClimbingStairs(int[] cost) { return reach(cost, cost.length); } // cheapest cost to stand on position i (n = the top) private int reach(int[] cost, int i) { if (i <= 1) return 0; // free starting steps int fromOne = reach(cost, i - 1) + cost[i - 1]; int fromTwo = reach(cost, i - 2) + cost[i - 2]; return Math.min(fromOne, fromTwo); }
Correct and obvious, but exponential — times out long before n = 1000.
BetterMemoized Recursion (Top-Down)
O(n)Space O(n)There are only n+1 distinct positions, so cache each answer the first
time it is computed. Every later call for the same position becomes an O(1) lookup,
collapsing the exponential tree into a linear chain.
public int minCostClimbingStairs(int[] cost) { int[] memo = new int[cost.length + 1]; Arrays.fill(memo, -1); return reach(cost, cost.length, memo); } private int reach(int[] cost, int i, int[] memo) { if (i <= 1) return 0; if (memo[i] != -1) return memo[i]; int fromOne = reach(cost, i - 1, memo) + cost[i - 1]; int fromTwo = reach(cost, i - 2, memo) + cost[i - 2]; memo[i] = Math.min(fromOne, fromTwo); return memo[i]; }
Linear time, but keeps an O(n) memo plus an O(n) recursion stack.
OptimalBottom-Up with Two Variables
O(n)Space O(1)Fill the table from position 2 upward instead of recursing down.
Since reach(i) only reads the two previous entries, two rolling variables
(prev2, prev1) replace the whole array.
public int minCostClimbingStairs(int[] cost) { int prev2 = 0; // reach(i-2) int prev1 = 0; // reach(i-1) for (int i = 2; i <= cost.length; i++) { int cur = Math.min(prev1 + cost[i - 1], prev2 + cost[i - 2]); prev2 = prev1; prev1 = cur; } return prev1; }
Dry runcost = [10,15,20]
- base00····cost=[1,100,1,1,100]
- i=2001i···min(0+100, 0+1)=1
- i=30012i··min(1+1, 0+100)=2
- i=400122i·min(2+1, 1+1)=2
- i=5001223imin(2+100, 2+1)=3 ✔
Linear time, constant memory, no recursion — the answer interviewers want.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Plain Recursion | O(2n) | O(n) |
| Better | Memoized Recursion (Top-Down) | O(n) | O(n) |
| Optimal | Bottom-Up with Two Variables | O(n) | O(1) |
- Returning
reach(n-1)— the top is past the last step, indexn. - Charging a cost for the starting step — steps 0 and 1 are reached for free.
- Adding
cost[i]on arrival instead of the cost of the step you leave from.
- Define the state in words first: “cheapest cost to stand on position i”.
- Show the exponential recursion, point out repeated subproblems, then add the memo.
- Finish by noting only two previous values are read, so space drops to O(1).