Min Cost Climbing Stairs

1. Problem & Core Objective

cost[i] is the cost of stepping off stair i. You may start at index 0 or index 1, and each move climbs 1 or 2 stairs. Return the minimum cost to reach past the top (index n).

cost = [10,15,20]           →  15      start at 1, pay 15, jump 2 to the top
cost = [1,100,1,1,1,100,1,1,100,1]  →  6

Constraints: 2 <= cost.length <= 1000 · 0 <= cost[i] <= 999

What's actually being tested: the same recurrence shape as question 1 with min instead of + — counting uses addition, optimisation uses min or max. And two off-by-one traps: the destination is index n, not n−1, and you pay on leaving a stair, not arriving.

2. First-Principles Thought Process

The one-line change from Climbing Stairs

Question 1 counted paths: dp[i] = dp[i−1] + dp[i−2].

Here we optimise over paths: dp[i] = min(dp[i−1] + cost[i−1], dp[i−2] + cost[i−2]).

The combiner changes, the structure doesn't. That's worth stating as a general rule:

Defining the state precisely

Let dp[i] = the minimum cost to reach stair i, having not yet paid to leave it.

Then arriving at i means having been at i−1 and paid cost[i−1] to step off, or at i−2 and paid cost[i−2].

Getting this definition wrong — "cost to reach and leave i" — shifts everything by one term and produces a plausible wrong answer.

The two off-by-ones

The destination is index n, one past the last stair. cost.length = 3 means stairs 0, 1, 2 and a top at index 3. Returning dp[n−1] answers a different question.

Both starts are free. dp[0] = dp[1] = 0 — you may begin at either without paying, because the cost is charged on leaving.

Rolling to O(1)

Again a fixed two-cell window, so two variables suffice.

3. Solution Paths

Approach 1 — Recursion from the top

public int minCostClimbingStairs(int[] cost) {
    return minCost(cost, cost.length);
}

private int minCost(int[] cost, int i) {
    if (i <= 1) return 0;                          // both starts are free
    return Math.min(minCost(cost, i - 1) + cost[i - 1],
                    minCost(cost, i - 2) + cost[i - 2]);
}

• Time O(2^n) · Space O(n) stack

Counter-questions on this approach

⭐ "Why i <= 1 returns 0 rather than cost[i]?"

Because dp[i] is the cost to reach stair i, and you may start at index 0 or 1 for free. You haven't paid anything yet at that point — the payment happens when you step off.

Returning cost[i] would charge for the starting stair immediately, which double-counts: the recurrence already adds cost[i-1] or cost[i-2] when stepping from it.

⭐ "Why is this exponential, and what's the fix?"

Same as question 1 — minCost(i) is recomputed from both branches, so the call tree is O(2^n) over n distinct inputs. Memoising on i collapses it to O(n).

At n = 1000 the naive version is entirely infeasible.

"Why call with cost.length rather than cost.length - 1?"

Because the goal is to reach past the top — index n. With cost = [10,15,20] the stairs are 0, 1, 2 and the destination is 3. Calling with n − 1 would compute the cost to reach the last stair, which isn't the question.

It's the first thing I'd verify on the example: from index 1 pay 15 and jump two, landing on index 3. Answer 15 ✓

Approach 2 — Tabulation

public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int[] dp = new int[n + 1];                     // dp[n] is the destination
    dp[0] = 0; dp[1] = 0;                          // both starts are 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];
}

Trace — cost = [10,15,20]:

Answer dp[3] = 15 ✓

• Time O(n) · Space O(n)

Counter-questions on this approach

⭐ "Why is the array sized n + 1?"

Because the destination is index n, one past the final stair. An array of size n has no slot for it, and dp[n-1] answers "cheapest to reach the last stair" — a different question that happens to give a plausible number.

On [10,15,20] that would return 10 instead of 15.

⭐ "Why cost[i-1] rather than cost[i] in the first term?"

Because you pay to leave the stair you're on. Arriving at i from i−1 means stepping off stair i−1, so the charge is cost[i-1].

Using cost[i] would charge for the stair being arrived at, which is both wrong and would index out of bounds at i = n.

"Do you need both dp[0] = 0 and dp[1] = 0?"

They're the default for a fresh int[], so the assignments are documentation rather than necessity. I write them because the base case is the part most likely to be wrong, and stating it explicitly is worth the two lines.

Approach 3 — Rolling variables (optimal)

public int minCostClimbingStairs(int[] cost) {
    int twoBack = 0, oneBack = 0;                  // dp[0], dp[1]

    for (int i = 2; i <= cost.length; i++) {
        int current = Math.min(oneBack + cost[i - 1],
                               twoBack + cost[i - 2]);
        twoBack = oneBack;
        oneBack = current;
    }
    return oneBack;
}

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "Why is rolling valid here?"

Because dp[i] reads a fixed window — dp[i−1] and dp[i−2] — so everything older is dead. Two variables carry the whole state.

Same test as question 1: bounded lookback rolls, unbounded doesn't.

"Why return oneBack rather than current?"

After the final iteration oneBack holds dp[n]. current is scoped to the loop body. And if the loop never runs — cost.length exactly 2 would still run once, but conceptually — oneBack is dp[1] = 0, which is the right answer for a hypothetical empty staircase.

"Could the total overflow?"

Costs are at most 999 with at most 1000 stairs, so the maximum possible total is 999,000 — far inside int. Worth a moment's check rather than an assumption, but comfortably safe here.

"What if cost.length were 2?"

The loop runs once, for i = 2: min(dp[1] + cost[1], dp[0] + cost[0]) = min(cost[1], cost[0]). Correct — with two stairs you start on the cheaper one and jump straight past the top.

Comparison

4. Why the Optimal Wins

Identical to question 1 — the recursion recomputes n subproblems exponentially often, and the fix is the same pipeline.

What's worth carrying forward is the combiner substitution: the structure of the recurrence is determined by the problem's moves (1 or 2 steps), and the combiner is determined by what's being asked (count vs minimise). Recognising those as independent choices is what makes the next ten questions feel like variations rather than new problems.

The framing worth keeping:

Same recurrence, different combiner: + counts, min optimises. And define the state precisely — dp[i] is the cost to REACH stair i, because you pay on leaving, not arriving.

5. Java Prerequisites

Array sized for the destination

int[] dp = new int[n + 1];       // dp[n] is "past the top"

Paying on departure

dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);

cost[i-1] because you step off stair i−1 to reach i.

Rolling shuffle — compute current before overwriting.

Java array defaults — new int[n] is all zeros, so dp[0] = dp[1] = 0 is documentation.

6. Interview Communication Guide

Clarifying questions: Do I pay on arriving at a stair or leaving it (leaving — this is the crux)? Is the destination the last stair or past it (past it, index n)? Can I start at index 0 or 1 (either, free)? Can costs be zero (yes)?

The pitch

"This is the Climbing Stairs recurrence with one substitution: min instead of +. Counting paths uses addition; optimising over paths uses min. The structure comes from the allowed moves; the combiner comes from what's being asked.

I'd define the state carefully: dp[i] is the minimum cost to reach stair i, not having paid to leave it yet. Then arriving at i means being at i−1 and paying cost[i−1] to step off, or at i−2 and paying cost[i−2].

Two off-by-ones I'd call out. The destination is index n, one past the last stair — so the array is sized n+1, and returning dp[n−1] answers a different question. On [10,15,20] that would give 10 instead of 15.

And both starts are free, so dp[0] = dp[1] = 0. You haven't paid anything on the stair you begin on, because the charge is on leaving.

Then the usual pipeline: the naive recursion is O(2^n), memoising makes it O(n), tabulating removes the recursion, and since dp[i] reads only a fixed two-cell window, two variables replace the array — O(1) space.

Overflow isn't a concern: 1000 stairs at 999 each caps the total at 999,000."

Edge cases to volunteer:

Name [10,15,20]. It's the smallest case where returning dp[n−1] instead of dp[n] gives a wrong but plausible answer — 10 rather than 15.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the actual path, not just the cost."

Track which predecessor won at each step in a from[] array, then walk back from index n. O(n) extra space — and note this kills the rolling optimisation, since you now need the whole history.

That trade recurs: O(1) space and path reconstruction are mutually exclusive.

⭐ "Maximise the cost instead."

Swap min for max. Nothing else changes, which is the clearest demonstration that structure and combiner are independent.

"What if you could climb up to k stairs at a time?"

dp[i] = min over j in 1..k of (dp[i-j] + cost[i-j]). That's O(n · k) time, and the window is still fixed at k cells so it rolls with a circular buffer of size k. A sliding-window minimum (monotonic deque) gets it back to O(n).

"What if some stairs were broken?"

Set dp[i] = Integer.MAX_VALUE for a broken stair and guard against relaxing from it — otherwise MAX_VALUE + cost overflows negative and looks like a bargain. Same sentinel discipline as the graph problems.

"What if costs could be negative?"

min still works and the DP is unchanged, since each stair is used at most once along a path — there's no cycle to exploit. Worth noting because negative weights break Dijkstra but not a DAG DP like this one.

"What if n were 10^6?"

The rolling version is O(n) time and O(1) space, so it scales directly. The recursion would overflow the stack long before that, which is the practical argument for tabulating.