Min Cost Climbing Stairs

Problem in Plain English

Each step charges a fee when you leave it, and from any step you may climb one or two steps forward. Starting from step 0 or step 1, find the cheapest total fee that reaches the top just past the last step.

Problem Statement

You are given an integer array cost where cost[i] is the price you pay when you leave step i. From any step you may climb either one or two steps forward.

You may start on step 0 or step 1 without paying anything yet. Paying happens only when you leave a step you are standing on, so the starting step itself is free until you move.

Return the minimum total price needed to reach the top, which is the position just past the last index of cost (index n for an array of length n).

Constraints

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

Examples

Example 1

Input: cost = [10, 15, 20]
Output: 15

Start on step 1, pay 15, then climb two steps straight to the top.

Example 2

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6

Start at index 0 and leave paid indices 0, 2, 4, 6, 7, and 9, then reach the top at 10. Their six fees are all 1; the jumps are 2, 2, 2, 1, 2, and 1. The one-step jump from 6 to 7 is necessary to skip index 8. The minimum-cost recurrence confirms that no route costs less than 6.

Example 3

Input: cost = [0, 999]
Output: 0

With only two steps, start at index 0, pay its zero fee, and jump two steps to top index 2. Starting at index 1 would pay 999, so the answer is 0. A free start does not waive a departure fee; here that fee happens to be zero.

Intuition

A route pays only for the steps it leaves, so skipping an expensive step can be cheaper than taking more short moves. In [10, 15, 20], starting at step 1 and jumping to the top pays 15; starting at step 0 costs at least 25. To reach any position, the last move must come from one of its two predecessors. Compare the cheapest cost to reach each predecessor plus its departure fee. Those two choices contain every possible final move, and only their two best costs need to be remembered.

Approaches

Recursive Branching

Solution Details

Reveal Recursive Branching: intuition, complexity, and code

Intuition

Try both possible jumps from every step and keep the cheaper remaining route. Define dfs(i) as the minimum additional fee from standing at i to the top; the fee at i is still unpaid. For [10, 15, 20], dfs(0) returns 25 and dfs(1) returns 15, so choose the second free starting position. Repeated calls such as dfs(2) expose why uncached recursion becomes exponential.

Step-by-Step Logic

Define dfs(i) as the remaining departure fees from step i. Return zero whenever i reaches or passes cost.length; neither the top nor a position beyond it has a fee.
At a paid step, evaluate dfs(i + 1) and dfs(i + 2), choose the smaller continuation, and add cost[i]. In Example 1, dfs(2) evaluates two zero-cost base calls and returns 20.
Evaluate dfs(0) first. Its call for dfs(1) returns 15 + min(20, 0) = 15; its separate call for dfs(2) repeats the work and returns 20. Thus dfs(0) returns 10 + min(15, 20) = 25.
Evaluate dfs(1) again for the other allowed start; it repeats its child calls and returns 15. Return the minimum of the two starting results, 15 for Example 1.

Why It Works

At or beyond index n, no paid step remains, so the additional cost is zero. For a paid step i, every route first pays cost[i] and then moves to either i + 1 or i + 2. Taking the cheaper optimal continuation therefore gives exactly the cheapest route from i; induction backward from the top proves the recurrence. The two starting positions are the only allowed starts, so their minimum is the answer. The i >= n base also accepts a two-step jump past the top from the last step: with nonnegative fees, that adds no better route than the available one-step jump to the top, so the minimum remains unchanged.

Dry Run

Recursive Branching: variable states at each step
Execution event	Active call path	Child result / return
Enter first start	0	wait for 1 then 2
Enter left child	0 -> 1	wait for 2 then 3
Enter left child	0 -> 1 -> 2	wait for 3 then 4
Base call enters and returns	0 -> 1 -> 2 -> 3	0; step 2 saves left = 0
Base call enters and returns	0 -> 1 -> 2 -> 4	0
Combine and return	0 -> 1 -> 2	20 + min(0, 0) = 20; step 1 saves left = 20
Base call enters and returns	0 -> 1 -> 3	0
Combine and return	0 -> 1	15 + min(20, 0) = 15; step 0 saves left = 15
Enter repeated right child	0 -> 2	wait for 3 then 4
Base call enters and returns	0 -> 2 -> 3	0; step 2 saves left = 0
Base call enters and returns	0 -> 2 -> 4	0
Combine and return	0 -> 2	20 + min(0, 0) = 20
Return first start	0	10 + min(15, 20) = 25; save start0 = 25
Enter second start	1	wait for 2 then 3
Enter repeated left child	1 -> 2	wait for 3 then 4
Base call enters and returns	1 -> 2 -> 3	0; step 2 saves left = 0
Base call enters and returns	1 -> 2 -> 4	0
Combine and return	1 -> 2	20 + min(0, 0) = 20; step 1 saves left = 20
Base call enters and returns	1 -> 3	0
Return second start	1	15 + min(20, 0) = 15; save start1 = 15
Return answer	no active dfs	min(25, 15) = 15

Complexity Analysis

Time Complexity

O(2^n)

Space Complexity

O(n)

Let n be cost.length. The call-count recurrence branches to suffixes of lengths m - 1 and m - 2, so growth is exponential, more tightly Theta(phi^n) for the golden ratio phi; O(2^n) is a loose upper bound, not exact doubling at each level. The deepest path contains O(n) active stack frames, each with constant local storage. There is no memo array, input copy, or mutation. Plain recursion is a teaching baseline: n = 1000 is infeasible in time and may exceed Python recursion depth. Use the iterative approach for the full bound. Any route pays at most n fees of at most 999, so even intermediate totals are at most 999000 and fit signed 32-bit integers.

Code

Solution.java

1class Solution {2    public int minCostClimbingStairs(int[] cost) {3        return Math.min(dfs(cost, 0), dfs(cost, 1));4    }5
6    private int dfs(int[] cost, int i) {7        // At or beyond the top, there is no remaining departure fee.8        if (i >= cost.length) return 0;9        return cost[i] + Math.min(dfs(cost, i + 1), dfs(cost, i + 2));10    }11}

Hints

Hint 1

To reach step i you must arrive from step i - 1 or step i - 2, so the answer for i depends only on those two earlier answers.

Hint 2

Write the recurrence as dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]) with dp[0] = dp[1] = 0, and fill it from left to right.

Hint 3

Only the last two table values are ever read, so two rolling variables can replace the whole array.

Edge Cases

At length 2, one jump from either allowed start reaches the top. The answer is min(cost[0], cost[1]), including [0, 999] -> 0.
All fees zero gives zero even though many routes tie. Both branches must remain legal; zero is a valid cost, not an uncomputed sentinel.
The last paid step can be skipped: [10, 15, 20] costs 15 by leaving index 1 and landing at top index 3.
Alternating large and small fees can require switching jump lengths; the ten-step example pays indices 0, 2, 4, 6, 7, 9, not simply every other index.
At n = 1000 with every fee 999, the cheapest route pays for 500 departures and costs 499500. Rolling variables handle it without stack growth; uncached recursion is impractical.

Common Mistakes and Interview Tips

Charging the destination instead of the departure step mixes two DP state definitions. An arrival-cost state adds cost[i - 1] or cost[i - 2], never cost[i].
Initializing arrival costs with cost[0] and cost[1] charges the starts too early. Starting is free, but leaving whichever start you choose still pays its fee; initialize arrival states to zero.
Stopping before i = n returns the cost of reaching the last paid step, rather than the top. The loop must include n, but must never read cost[n].
Overwriting prev2 before computing cur loses the i - 2 arrival cost; compute both candidates first, then shift.
Always taking the locally cheaper next fee is not a proof of the cheapest complete route. A choice changes which future steps can be skipped, so compare full continuation or arrival costs.
Assuming a recursive recurrence is efficient without memoization repeats suffixes exponentially; the n = 1000 limit requires the iterative approach shown here.

Key Takeaway

When the best value at position i depends only on a fixed window of earlier positions, fill a 1D table left to right and then shrink the window to a few rolling variables.