Skip to main content
CodePeetCodePeet
CodePeet 250

Min Cost Climbing Stairs

EASYProblemSolveExternal Links

Description

You are given an integer array cost where cost[i] represents the price you must pay to step on the i-th stair. Once you pay the cost of a particular stair, you are allowed to climb either one step or two steps upward from that position.

You may choose to begin your climb from either stair 0 or stair 1 — stepping onto your chosen starting stair is free, but you must pay its cost before climbing further.

The goal is to reach the top of the floor, which is the position just beyond the last stair in the array. Return the minimum total cost needed to reach the top.

Examples

Example 1

Input: cost = [10, 15, 20]

Output: 15

Explanation: Start at stair 1 (cost 15). From stair 1, climb two steps to reach the top. Total cost = 15. Alternatively, starting at stair 0 costs 10, then you could climb to stair 2 (cost 20) and then to the top for a total of 30, or climb to stair 1 (cost 15) and then to the top for 25. Starting at stair 1 and jumping directly to the top gives the minimum cost of 15.

Example 2

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

Output: 6

Explanation: Start at stair 0 (cost 1). Jump two steps to stair 2 (cost 1). Jump two steps to stair 4 (cost 1). Jump two steps to stair 6 (cost 1). Jump one step to stair 7 (cost 1). Jump two steps to stair 9 (cost 1). Jump one step to the top. Total cost = 1 + 1 + 1 + 1 + 1 + 1 = 6. The strategy avoids the expensive stairs (cost 100) by jumping over them whenever possible.

Example 3

Input: cost = [0, 0]

Output: 0

Explanation: Both stairs have zero cost. Start at stair 0 (cost 0), climb two steps to the top. Total cost = 0. Starting at stair 1 also works with the same cost.

Constraints

  • 2 ≤ cost.length ≤ 1000
  • 0 ≤ cost[i] ≤ 999

Editorial

Brute Force - Recursion

Intuition

The most natural way to think about this problem is to explore every possible path from the bottom to the top and pick the cheapest one.

At each stair, you face a choice: climb one step or climb two steps. This creates a branching decision tree. If we define a function dfs(i) as the minimum cost to reach the top starting from stair i, then:

  • If i is past the last stair (i.e., i ≥ n), we have reached the top — cost is 0.
  • Otherwise, we must pay cost[i] and then choose the cheaper option between climbing one step (dfs(i + 1)) or two steps (dfs(i + 2)).

So the recurrence is: dfs(i) = cost[i] + min(dfs(i + 1), dfs(i + 2)).

Since we can start at either stair 0 or stair 1, the final answer is min(dfs(0), dfs(1)).

This approach is correct but extremely slow. The recursion tree branches at every step, leading to an exponential number of calls. Crucially, many subproblems are computed repeatedly — for example, dfs(2) gets called from both dfs(0) and dfs(1), and each of those calls spawns its own subtree. This overlapping subproblem structure is what makes the brute force impractical for larger inputs.

Step-by-Step Explanation

Let's trace through with cost = [10, 15, 20], n = 3. We need min(dfs(0), dfs(1)).

Step 1: Start by calling dfs(0). We pay cost[0] = 10 and need min(dfs(1), dfs(2)).

Step 2: Expand dfs(1) under dfs(0). We pay cost[1] = 15 and need min(dfs(2), dfs(3)).

Step 3: Expand dfs(2) under dfs(1). We pay cost[2] = 20 and need min(dfs(3), dfs(4)).

Step 4: dfs(3) hits base case (3 ≥ 3), returns 0. dfs(4) also hits base case (4 ≥ 3), returns 0.

Step 5: Resolve dfs(2) = 20 + min(0, 0) = 20.

Step 6: Back in dfs(1): dfs(3) is a base case = 0. So dfs(1) = 15 + min(20, 0) = 15.

Step 7: Now expand dfs(2) under dfs(0) — but wait, we already computed dfs(2) = 20 inside dfs(1)! Without memoization, we recompute it from scratch: expand dfs(3) = 0, dfs(4) = 0, get dfs(2) = 20 again. This is wasted work.

Step 8: Resolve dfs(0) = 10 + min(15, 20) = 25.

Step 9: Now compute dfs(1) for the top-level min. This was already computed inside dfs(0) as 15, but brute force recomputes it: dfs(1) = 15 + min(dfs(2), dfs(3)) = 15 + min(20, 0) = 15. More redundant work.

Step 10: Final answer = min(dfs(0), dfs(1)) = min(25, 15) = 15.

Brute Force Recursion — Exponential Branching with Redundant Calls — Watch how the recursion tree expands, computing the same subproblems multiple times. Notice dfs(2) is calculated twice — once under dfs(1) and once directly under dfs(0).

Algorithm

  1. Define a recursive function dfs(i) that returns the minimum cost to reach the top from stair i.
  2. Base case: If i ≥ n (past the last stair), return 0 — you have reached the top.
  3. Recursive case: Return cost[i] + min(dfs(i + 1), dfs(i + 2)) — pay the current stair's cost and pick the cheaper of climbing one or two steps.
  4. The final answer is min(dfs(0), dfs(1)), since you can start at either stair.

Code

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        return min(dfs(cost, 0, n), dfs(cost, 1, n));
    }
    
    int dfs(vector<int>& cost, int i, int n) {
        // Base case: reached or passed the top
        if (i >= n) return 0;
        
        // Pay current cost, pick cheaper of 1-step or 2-step climb
        return cost[i] + min(dfs(cost, i + 1, n), dfs(cost, i + 2, n));
    }
};
class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        n = len(cost)
        
        def dfs(i: int) -> int:
            # Base case: reached or passed the top
            if i >= n:
                return 0
            
            # Pay current cost, pick cheaper of 1-step or 2-step climb
            return cost[i] + min(dfs(i + 1), dfs(i + 2))
        
        return min(dfs(0), dfs(1))
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        return Math.min(dfs(cost, 0), dfs(cost, 1));
    }
    
    private int dfs(int[] cost, int i) {
        // Base case: reached or passed the top
        if (i >= cost.length) return 0;
        
        // Pay current cost, pick cheaper of 1-step or 2-step climb
        return cost[i] + Math.min(dfs(cost, i + 1), dfs(cost, i + 2));
    }
}

Complexity Analysis

Time Complexity: O(2^n)

At each stair, the function branches into two recursive calls (climb 1 or climb 2). Without memoization, the same subproblems are recomputed exponentially many times. The recursion tree has up to 2^n leaves, making this approach impractical for arrays longer than about 30 elements.

Space Complexity: O(n)

The recursion call stack can grow up to depth n in the worst case (if we take single steps all the way). No additional data structures are used.

Why This Approach Is Not Efficient

The brute force recursion has exponential time complexity O(2^n) because it recomputes the same subproblems over and over. In our trace of cost = [10, 15, 20], dfs(2) was computed twice and dfs(3) was computed three times. For a cost array of length 1000, the number of redundant calls becomes astronomically large — far exceeding any reasonable time limit.

The root cause is overlapping subproblems: dfs(i) is needed by both dfs(i - 1) and dfs(i - 2), creating a cascading duplication pattern identical to the Fibonacci sequence recursion.

The fix is to remember results we have already computed. If we store dfs(i) the first time it is calculated, we can return the cached value instantly on subsequent calls. This eliminates all redundant computation, reducing the total unique subproblems from exponentially many to exactly n.

Better Approach - Bottom-Up Dynamic Programming

Intuition

Instead of solving the problem top-down with recursion, we can flip the perspective and solve it bottom-up. We define dp[i] as the minimum cost to reach position i.

Since you can start at stair 0 or stair 1 for free, we set dp[0] = 0 and dp[1] = 0. For every position i ≥ 2, you can arrive from either one step below (position i - 1, paying cost[i - 1]) or two steps below (position i - 2, paying cost[i - 2]). So:

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

The "top of the floor" is position n (one step past the last stair at index n - 1), so the answer is dp[n].

Think of it as building a table from left to right. Each cell only depends on the two cells before it, so by the time we reach cell i, both dependencies are already solved. There is no redundancy — each subproblem is computed exactly once.

Step-by-Step Explanation

Let's trace through with cost = [10, 15, 20], n = 3. The dp table has indices 0 through 3, where 3 represents the top.

Step 1: Initialize the dp table with n + 1 = 4 entries, all initially unknown.

Step 2: Set dp[0] = 0 and dp[1] = 0. We can stand on stair 0 or stair 1 for free.

Step 3: Compute dp[2]. We can reach position 2 from position 0 (paying cost[0] = 10) or from position 1 (paying cost[1] = 15).

  • Option A: dp[0] + cost[0] = 0 + 10 = 10
  • Option B: dp[1] + cost[1] = 0 + 15 = 15
  • dp[2] = min(10, 15) = 10

Step 4: Compute dp[3] (the top). We can reach it from position 1 (paying cost[1] = 15) or from position 2 (paying cost[2] = 20).

  • Option A: dp[1] + cost[1] = 0 + 15 = 15
  • Option B: dp[2] + cost[2] = 10 + 20 = 30
  • dp[3] = min(15, 30) = 15

Step 5: The answer is dp[3] = 15. The cheapest path is: start at stair 1, pay 15, jump two steps directly to the top.

Bottom-Up DP — Filling the Table Left to Right — Watch how we fill the dp table iteratively. Each cell depends on the two cells before it, so we always have all the information we need.

Algorithm

  1. Create a dp array of size n + 1, where n = cost.length.
  2. Set dp[0] = 0 and dp[1] = 0 (free to start at either stair).
  3. For each position i from 2 to n:
    • dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
  4. Return dp[n] (the minimum cost to reach the top).

Code

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp(n + 1, 0);
        
        // dp[0] = 0, dp[1] = 0 (already initialized)
        
        for (int i = 2; i <= n; i++) {
            dp[i] = min(dp[i - 1] + cost[i - 1],
                        dp[i - 2] + cost[i - 2]);
        }
        
        return dp[n];
    }
};
class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        n = len(cost)
        dp = [0] * (n + 1)
        
        # dp[0] = 0, dp[1] = 0 (free starting positions)
        
        for i in range(2, n + 1):
            dp[i] = min(dp[i - 1] + cost[i - 1],
                        dp[i - 2] + cost[i - 2])
        
        return dp[n]
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        
        // dp[0] = 0, dp[1] = 0 (already initialized)
        
        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];
    }
}

Complexity Analysis

Time Complexity: O(n)

We fill the dp table from index 2 to n, performing a constant amount of work (one comparison and one addition) per entry. This gives exactly n - 1 iterations, which is O(n).

Space Complexity: O(n)

We allocate a dp array of size n + 1 to store the minimum cost at each position. This is a massive improvement over the brute force's exponential time, but we can do better on space.

Why This Approach Is Not Efficient

The bottom-up DP approach achieves optimal O(n) time complexity, but it uses O(n) extra space for the dp array. For an array with 1000 elements, that means allocating 1001 integers just to track intermediate results.

However, if we look at the recurrence dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]), we notice that each cell only depends on the two immediately preceding cells. We never look back further than two positions. This means we do not need to keep the entire table in memory — we only need to remember the last two values.

By replacing the full array with just two rolling variables, we can reduce the space complexity from O(n) to O(1) while maintaining the same O(n) time complexity.

Optimal Approach - Space-Optimized Dynamic Programming

Intuition

The key observation from the bottom-up approach is that dp[i] only ever looks at dp[i - 1] and dp[i - 2]. We never revisit older cells. This means we can replace the entire array with just two variables: prev2 (representing dp[i - 2]) and prev1 (representing dp[i - 1]).

As we iterate from position 2 to n, we compute the current value using these two variables, then slide the window forward: the old prev1 becomes the new prev2, and the newly computed value becomes the new prev1.

This is the same trick used in the space-optimized Fibonacci computation: since each value depends only on the two before it, you only need a sliding window of size 2.

The result is an algorithm that runs in O(n) time with O(1) extra space — the best possible for this problem.

Step-by-Step Explanation

Let's trace through with cost = [10, 15, 20], n = 3.

Step 1: Initialize two rolling variables: prev2 = 0 (representing dp[0]) and prev1 = 0 (representing dp[1]).

Step 2: Process i = 2. We compute the cost to reach position 2:

  • From position 0: prev2 + cost[0] = 0 + 10 = 10
  • From position 1: prev1 + cost[1] = 0 + 15 = 15
  • current = min(10, 15) = 10

Step 3: Slide the window: prev2 = 0 → becomes old prev1 = 0. prev1 = 0 → becomes current = 10. Now prev2 = 0, prev1 = 10.

Step 4: Process i = 3 (the top). We compute the cost to reach the top:

  • From position 1: prev2 + cost[1] = 0 + 15 = 15
  • From position 2: prev1 + cost[2] = 10 + 20 = 30
  • current = min(15, 30) = 15

Step 5: Slide the window: prev2 = 10, prev1 = 15.

Step 6: We've reached the top. The answer is prev1 = 15. We used only two extra variables — no array needed.

Space-Optimized DP — Rolling Two Variables Across the Cost Array — Watch how two variables (prev2 and prev1) slide through the cost array, computing each position's minimum cost without storing the full dp table.

Algorithm

  1. Initialize two variables: prev2 = 0 and prev1 = 0 (representing dp[0] and dp[1]).
  2. For each position i from 2 to n:
    • Compute current = min(prev1 + cost[i - 1], prev2 + cost[i - 2])
    • Update: prev2 = prev1, prev1 = current
  3. Return prev1 (which now represents dp[n], the minimum cost to reach the top).

Code

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        int prev2 = 0;  // dp[i-2]
        int prev1 = 0;  // dp[i-1]
        
        for (int i = 2; i <= n; i++) {
            int current = min(prev1 + cost[i - 1],
                              prev2 + cost[i - 2]);
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
};
class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        n = len(cost)
        prev2 = 0  # dp[i-2]
        prev1 = 0  # dp[i-1]
        
        for i in range(2, n + 1):
            current = min(prev1 + cost[i - 1],
                          prev2 + cost[i - 2])
            prev2 = prev1
            prev1 = current
        
        return prev1
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int prev2 = 0;  // dp[i-2]
        int prev1 = 0;  // dp[i-1]
        
        for (int i = 2; i <= n; i++) {
            int current = Math.min(prev1 + cost[i - 1],
                                   prev2 + cost[i - 2]);
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate from position 2 to n exactly once, performing a constant number of operations per iteration (one comparison, one addition, two assignments). Total operations: n - 1, which is O(n). This is the best possible time complexity since we must examine every element of the cost array at least once.

Space Complexity: O(1)

We use only two extra integer variables (prev2 and prev1) regardless of input size. No array, no recursion stack, no hash map. This is optimal space usage — we cannot solve the problem with less than O(1) additional memory.