Min Cost Climbing Stairs — Adding a Cost Function to Fibonacci DP

Problem Statement#

You are given an integer array cost where cost[i] is the cost of the i-th step on a staircase. Once you pay the cost, you can either climb one or two steps. You can either start from the step with index 0, or the step with index 1. Return the minimum cost to reach the top of the floor (one step beyond the last element).

Constraints:

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

Example 1:

Input:  cost = [10, 15, 20]
Output: 15
Explanation: Start at index 1, pay 15, jump 2 steps to the top.

Example 2:

Input:  cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Take the cheap path: indices 0,2,4,6,8 each cost 1.
             Total = 6. Skip the expensive 100-cost steps.

Example 3:

Input:  cost = [0, 0, 0, 1]
Output: 0
Explanation: Start at index 0 (cost 0), jump 2 to index 2 (cost 0),
             jump 2 beyond the array. Total = 0.

Why This Problem Matters#

Min Cost Climbing Stairs is the direct sequel to Climbing Stairs (LC 70) and a favourite at Amazon and Google for exactly that reason: it tests whether you can adapt a recurrence you already know when the problem's objective shifts from counting to optimizing. The skeleton — "you arrive from i-1 or i-2" — is identical, but the operator changes from sum to min and each landing now has a price tag.

This problem also introduces the "virtual top" concept in DP: the goal position does not exist in the cost array. You are aiming for index n, one slot beyond the last element. Many DP problems use this device — a sentinel target one position past the data — and getting comfortable with it here pays dividends on problems like Perfect Squares and Word Break.

Interviewers also use this problem to test careful reading. The most common wrong answer comes from candidates who assume you pay when you land, when in fact you pay when you leave. A single-sentence clarification at the start of the problem separates strong candidates from the rest.

The Core Insight#

Define dp[i] as the minimum cost to step off (leave) step i. To leave step i, you must first arrive there — from step i-1 or step i-2 — and then pay cost[i].

Recurrence: dp[i] = cost[i] + min(dp[i-1], dp[i-2]).

The top of the staircase is one step beyond the array: you can reach it by leaving step n-1 (one step) or leaving step n-2 (two steps). The answer is therefore min(dp[n-1], dp[n-2]).

Base cases: dp[0] = cost[0] (you land on step 0 and pay to leave), dp[1] = cost[1].

Optimal substructure: the minimum cost to leave step i depends only on the minimum costs to leave steps i-1 and i-2, both of which are strictly smaller subproblems.

Overlapping subproblems: a naive recursion recomputes the same steps repeatedly.

Building the DP Solution#

Step 1 — Naive Recursion (Exponential)#

# Python — naive recursion, illustrative only
def minCostClimbingStairs(cost):
    n = len(cost)
    def leave(i):
        if i < 2:
            return cost[i]
        return cost[i] + min(leave(i - 1), leave(i - 2))
    return min(leave(n - 1), leave(n - 2))

// JavaScript — naive recursion
function minCostClimbingStairs(cost) {
    const n = cost.length;
    function leave(i) {
        if (i < 2) return cost[i];
        return cost[i] + Math.min(leave(i - 1), leave(i - 2));
    }
    return Math.min(leave(n - 1), leave(n - 2));
}

This recomputes leave(i) for the same i many times. Time is O(2^n).

Step 2 — Top-Down Memoization (O(n) time, O(n) space)#

# Python — top-down memoization
from functools import lru_cache
 
class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        n = len(cost)
 
        @lru_cache(maxsize=None)
        def dp(i: int) -> int:
            if i < 2:
                return cost[i]
            return cost[i] + min(dp(i - 1), dp(i - 2))
 
        return min(dp(n - 1), dp(n - 2))

// JavaScript — top-down memoization
var minCostClimbingStairs = function(cost) {
    const n = cost.length;
    const memo = new Map();
 
    function dp(i) {
        if (i < 2) return cost[i];
        if (memo.has(i)) return memo.get(i);
        const result = cost[i] + Math.min(dp(i - 1), dp(i - 2));
        memo.set(i, result);
        return result;
    }
 
    return Math.min(dp(n - 1), dp(n - 2));
};

Step 3 — Bottom-Up Tabulation (O(n) time, O(n) space)#

# Python — bottom-up tabulation
class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        n = len(cost)
        dp = [0] * n
        dp[0] = cost[0]
        dp[1] = cost[1]
        for i in range(2, n):
            dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])
        return min(dp[n - 1], dp[n - 2])

// JavaScript — bottom-up tabulation
var minCostClimbingStairs = function(cost) {
    const n = cost.length;
    const dp = new Array(n).fill(0);
    dp[0] = cost[0];
    dp[1] = cost[1];
    for (let i = 2; i < n; i++) {
        dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
    }
    return Math.min(dp[n - 1], dp[n - 2]);
};

Optimized Solution#

Since dp[i] depends only on dp[i-1] and dp[i-2], compress the table to two rolling variables:

# Python — space-optimized, O(n) time, O(1) space
class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        a, b = cost[0], cost[1]
        for i in range(2, len(cost)):
            a, b = b, cost[i] + min(a, b)
        return min(a, b)

// JavaScript — space-optimized, O(n) time, O(1) space
var minCostClimbingStairs = function(cost) {
    let a = cost[0], b = cost[1];
    for (let i = 2; i < cost.length; i++) {
        [a, b] = [b, cost[i] + Math.min(a, b)];
    }
    return Math.min(a, b);
};

Visual Dry Run#

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] (n = 10)

Answer = min(dp[8], dp[9]) = min(104, 6) = 6. The optimal path skips all the expensive steps.

Complexity Analysis#

Common Mistakes#

1. Thinking you pay to land, not to leave. The problem says you pay cost[i] and then can climb. Cost is incurred when departing step i, not arriving. Misreading this produces an off-by-one recurrence.

2. Returning dp[n-1] instead of min(dp[n-1], dp[n-2]). The top is one position past the last element. You can reach it by departing either of the last two steps. Many candidates return only dp[n-1] and miss the cheaper path through dp[n-2].

3. Starting the rolling variable loop at the wrong index. If you initialize a = cost[0], b = cost[1], the loop must start at i = 2. Starting at 0 or 1 corrupts the base cases.

4. Forgetting that n = 2 is the minimum. When cost has exactly 2 elements, the loop body never executes. The code returns min(cost[0], cost[1]) naturally — verify this works before submitting.

5. Confusing the "pay-to-leave" with adding a virtual dp[n] = 0. An alternative formulation appends a zero-cost virtual step: dp[n] = min(dp[n-1], dp[n-2]) with cost[n] = 0. Both formulations give the same answer; choose one and be consistent. Mixing them produces double-counting.

6. Confusing this with Climbing Stairs counting. In LC 70, the recurrence sums the two previous counts. Here it takes the minimum and adds the current cost. Same structure, different operator — do not copy the LC 70 solution.

Interview Tips#

Restate the cost direction before coding. Say: "I want to confirm — cost[i] is paid when leaving step i, not when arriving, correct?" This one clarification signals careful problem reading and prevents the most common bug.

Walk through the "virtual top" design choice. Explain why you return min(dp[n-1], dp[n-2]) rather than dp[n]: there is no step n in the array, and you can reach the top from either of the last two steps.

Show the full three-phase evolution — naive recursion, memoization, tabulation — even if you plan to submit the space-optimized version. FAANG interviewers reward DP fluency, and showing the evolution demonstrates understanding rather than pattern matching.

Contrast with LC 70. Interviewers may ask "how does this differ from Climbing Stairs?" The answer: LC 70 sums (counts paths); this problem takes min (minimizes cost). Same recurrence structure, different operator, additional cost function.

Follow-up Questions#

Q: What if you can take 1, 2, or 3 steps? Keep three rolling variables: c = cost[i] + min(a, b, c_prev). The approach generalizes to any fixed step size.

Q: What if you want to recover the actual path, not just the cost? Track a parent array: parent[i] = i - 1 if dp[i-1] is cheaper, else parent[i] = i - 2. Reconstruct the path by following parent pointers backward from the step before the top.

Q: What if step costs can change dynamically with updates? The simple linear DP requires recomputing from the updated index. For frequent updates, a segment tree over dp values supports O(log n) updates and O(1) queries — but this is an advanced extension beyond typical interviews.

Q: What if start positions have their own entry costs? Add entry costs to dp[0] and dp[1] as part of the base case. The recurrence is unchanged.

Q: What if the cost array is empty? The problem guarantees cost.length >= 2, but defensively return 0 for an empty array since there is no staircase to climb.

Key Takeaways#

• Define dp[i] precisely as "minimum cost to leave step i." The direction of cost payment (leave, not land) is everything.
• Recurrence: dp[i] = cost[i] + min(dp[i-1], dp[i-2]) — same Fibonacci structure as Climbing Stairs, but with a min operator and a cost factor.
• The final answer is min(dp[n-1], dp[n-2]) because the virtual top is reachable from either of the last two steps.
• Space-optimize with two rolling variables: a, b = cost[0], cost[1], then iterate from index 2.
• This is the first problem in the 1D DP curriculum where "counting paths" becomes "minimizing cost" — mastering the transition between these two modes is a key interview skill.
• The same pattern drives LC 198 House Robber (max instead of min), LC 931 Minimum Falling Path Sum (2D extension), and any problem where you optimize over Fibonacci-style choices.