#746 Min Cost Climbing Stairs
the problem
In plain words
Stair i costs cost[i] to step on. After paying for a stair you may climb one or two stairs. You may start on stair 0 or stair 1 for free, and the top is the spot just past the last stair. Return the cheapest total cost to reach the top.
in cost = [10,15,20]
out 15
Start on stair 1, pay 15, climb two stairs to the top.
in cost = [1,100,1,1,1,100,1,1,100,1]
out 6
Step only on the 1s: stairs 0, 2, 4, 6, 7, 9.
- 2 ≤ cost.length ≤ 1000
- 0 ≤ cost[i] ≤ 999
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
pattern1D DP
To stand on stair i you came from stair i − 1 (and paid for it) or from stair i − 2 (and paid for that). So reach(i) = min(reach(i − 1) + cost[i − 1], reach(i − 2) + cost[i − 2]) — Climbing Stairs with min instead of +.
solutions
From brute force to optimal
reach(i) = cheapest cost to stand on stair i; the answer is reach(n), the top.
- reach(0) = reach(1) = 0: starting is free.
- Otherwise try arriving from i − 1 and from i − 2, take the cheaper.
Two calls per stair, like Fibonacci (≈ 1.618ⁿ calls).
Recursion depth n.
class Solution { public int minCostClimbingStairs(int[] cost) { return reach(cost, cost.length); // the top is one step past the last stair } /** Cheapest total cost to stand on stair i. */ private int reach(int[] cost, int i) { if (i <= 1) return 0; // you may start on stair 0 or stair 1 for free // you arrived from i-1 (and paid for it) or from i-2 (and paid for that one) return Math.min(reach(cost, i - 1) + cost[i - 1], reach(cost, i - 2) + cost[i - 2]); }}reach(i) only depends on i — cache it.
- memo filled with −1 (0 is a real cost).
- Check, compute, store.
n + 1 states, O(1) each.
Memo + recursion stack.
class Solution { public int minCostClimbingStairs(int[] cost) { int[] memo = new int[cost.length + 1]; Arrays.fill(memo, -1); // -1 = not computed (0 is a real answer) 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]; return memo[i] = Math.min(reach(cost, i - 1, memo) + cost[i - 1], reach(cost, i - 2, memo) + cost[i - 2]); }}dp[i] = cheapest cost to stand on stair i, filled left to right.
- dp[0] = dp[1] = 0.
- dp[i] = min(dp[i − 1] + cost[i − 1], dp[i − 2] + cost[i − 2]) for i = 2..n.
- Return dp[n].
One loop, O(1) per stair.
The table of n + 1 ints.
class Solution { public int minCostClimbingStairs(int[] cost) { int n = cost.length; int[] dp = new int[n + 1]; // dp[i] = cheapest cost to stand on stair i (dp[n] = the top) // dp[0] = dp[1] = 0: starting there is free for (int i = 2; i <= n; i++) { dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); } return dp[n]; }}dp[i] reads only dp[i − 1] and dp[i − 2].
- prev2 = prev1 = 0.
- cur = min(prev1 + cost[i − 1], prev2 + cost[i − 2]); shift.
- Return prev1.
One pass.
Three ints.
class Solution { public int minCostClimbingStairs(int[] cost) { int prev2 = 0, prev1 = 0; // cheapest cost to stand on stair i-2 and on stair 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; }}in the room
How to say it in the interview
talk track
- Clarify first: the top is index n, one past the last stair, and the top itself costs nothing.
- "reach(i) = cheapest cost to stand on stair i; reach(0) = reach(1) = 0." Then the min recurrence.
- Squeeze to two variables, exactly like Climbing Stairs.
traps
- Returning reach(n − 1) instead of reach(n): the top is past the last stair.
- Charging for the starting stair twice, or charging for the top.
what they ask next
Follow-ups
Return the stairs you stepped on?
Keep the table and walk back from n, each time moving to whichever of i − 1 or i − 2 gave the minimum.
before you submit
Edge cases to test
- Two stairs → the cheaper of the two (start there, jump to the top).
- All costs 0 → 0.
- [0,1,2,2] → 2: skipping the last stair can be cheaper than stepping on it.
practise next
Similar problems
- #70Climbing StairsEasyin Dynamic Programming
- #198House RobberMediumin Dynamic Programming