Min Cost Climbing Stairs
Understanding the Problem
We have a staircase where each step has a cost. We want to reach "the top," which is one step beyond the last element in the array. At each step, we pay the cost at that step and then choose to climb either one or two steps forward. We can begin at step 0 or step 1.
The question is: what sequence of steps gives us the minimum total cost to reach the top?
This is a dynamic programming problem because each decision (climb one or climb two) affects future options, and the optimal choice at each step depends on what comes next. To arrive at any step, you must have come from either one step back or two steps back, so the cheapest way to reach a step is the cheaper of those two incoming paths.
Key Constraints:
2 <= cost.length <= 1000--> With n up to 1000, the O(2^n) recursive solution is impractical, so we need a polynomial approach. An O(n) DP solves it comfortably.0 <= cost[i] <= 999--> Costs are non-negative, so taking extra steps never helps. A greedy "skip the expensive steps" rule is not sufficient: skipping one expensive step might force you to land on another expensive one. The DP weighs both incoming paths instead of committing locally.- With at most 1000 steps each below 1000, the total cost stays well under 10^6, so 32-bit
intcannot overflow.
Approach 1: Recursion (Brute Force)
Intuition
Think recursively. We want to reach the top (position n, one past the last step). From any step i, we can jump to i+1 or i+2 after paying cost[i]. So the minimum cost starting from step i is cost[i] plus the cheaper of the minimum cost from step i+1 and the minimum cost from step i+2.
Since we can start at step 0 or step 1, the answer is the minimum of starting from either.
This approach is correct but slow. Every call branches into two recursive calls, and the same subproblems get solved repeatedly.
Algorithm
- Define a recursive function
minCost(i)that returns the minimum cost to reach the top starting from stepi. - Base cases: if
i >= n(wherenis the length ofcost), return 0 because we have already reached or passed the top. - Recursive case: return
cost[i] + min(minCost(i + 1), minCost(i + 2)). - The answer is
min(minCost(0), minCost(1)).
Example Walkthrough
Code
- Time Complexity: O(2^n). At each step, we branch into two recursive calls. Without memoization, this creates a binary recursion tree of depth n with many overlapping subproblems recomputed every time.
- Space Complexity: O(n). The recursion stack goes at most n levels deep.
The bottleneck is that minCost(i) gets called with the same value of i many times. The next approach stores each result the first time it is computed, so it is never recomputed.
Approach 2: Memoized Recursion (Top-Down DP)
Intuition
The recursive solution computes the same subproblems repeatedly. Memoization fixes this: store the result of minCost(i) in a cache the first time we compute it, and return the cached value on all subsequent calls. This turns the exponential recursion into a linear one, because each of the n subproblems is solved exactly once.
The logic stays identical. We add a lookup table: if the answer for step i is already computed, return it immediately instead of recursing.
Algorithm
- Create a memo array of size
n, initialized to -1 (meaning "not yet computed"). - Define
minCost(i)the same as before, but before recursing, check ifmemo[i]is already filled. If so, return it directly. - After computing the result for step
i, store it inmemo[i]before returning. - The answer is
min(minCost(0), minCost(1)).
Example Walkthrough
Code
- Time Complexity: O(n). Each of the n subproblems is computed exactly once. Each computation does O(1) work.
- Space Complexity: O(n). The memo array takes O(n) space, and the recursion stack can go up to O(n) levels deep.
Memoization gives O(n) time, but the recursion stack still uses O(n) space. The next approach builds the solution bottom-up and removes the recursion entirely, dropping space to O(1).
Approach 3: Bottom-Up DP with Space Optimization
Intuition
The top-down view asks "what is the cheapest way to reach the top from step i?" The bottom-up view flips it: "what is the cheapest way to reach step i from the bottom?"
Define dp[i] as the minimum cost to reach step i. To arrive at step i, we must have come from either step i-1 (paying cost[i-1]) or step i-2 (paying cost[i-2]). So dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]).
The base cases are dp[0] = 0 and dp[1] = 0, since we can start at either step without paying first. The answer is dp[n]. Because dp[i] only depends on the two preceding values, we can collapse the entire table into two rolling variables.
Computing dp[i] reads only dp[i-1] and dp[i-2], never anything older. Once dp[i] is computed, dp[i-2] is no longer needed by any future step. Keeping prev1 = dp[i-1] and prev2 = dp[i-2] and shifting them forward each iteration preserves exactly the two values the recurrence needs.
This is the same constant-space trick used for Fibonacci numbers, which also depends on its two previous values, with an added cost term at each step here.
Algorithm
- Initialize
prev2 = 0(cost to reach step 0) andprev1 = 0(cost to reach step 1). - For each step
ifrom 2 ton: - Compute
current = min(prev1 + cost[i-1], prev2 + cost[i-2]). - Shift:
prev2 = prev1,prev1 = current. - Return
prev1, which now holdsdp[n].
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the array once, doing O(1) work per step.
- Space Complexity: O(1). We use only two variables (
prev1andprev2) regardless of input size. No recursion stack, no DP array.