Min Cost Climbing Stairs: Bottom-Up DP

You are given an integer array cost where cost[i] is the cost of stepping on the ith step of a staircase. Once you pay the cost, you can climb either one or two steps. You can start from step 0 or step 1. Find the minimum cost to reach the top of the staircase (one step past the last index).

This is LeetCode 746: Min Cost Climbing Stairs, and it is one of the best follow-ups to Climbing Stairs. Same staircase, same 1-or-2 jump mechanic, but now each step has a price. Your job is to find the cheapest path to the top.

Why this problem matters

If Climbing Stairs teaches you the structure of linear DP, Min Cost Climbing Stairs teaches you how to optimize within that structure. In Climbing Stairs you count ways. Here you minimize cost. That shift from counting to optimization is exactly what separates easy DP from medium DP.

The recurrence looks almost identical, but instead of adding, you take the minimum. That single change shows up in a huge number of problems: House Robber, Coin Change, minimum path sum, and many others. Getting comfortable with it here, on a problem where the staircase is already familiar, makes those harder problems much more approachable.

Starting with recursion

Think about what it costs to reach step i. You must pay cost[i] to stand on it, and you could have arrived from step i-1 or step i-2. You want whichever arrival is cheaper. The top of the staircase is one position past the last index, so the final answer is the minimum of reaching step n-1 and reaching step n-2.

def min_cost_climbing_stairs(cost):
    def helper(i):
        if i < 2:
            return cost[i]
        return cost[i] + min(helper(i - 1), helper(i - 2))

    n = len(cost)
    return min(helper(n - 1), helper(n - 2))

This works, but it is slow. The recursion tree branches at every step, recomputing the same subproblems many times. For a cost array of length 40, you are looking at billions of calls. Time complexity: O(2^n).

Bottom-up DP approach

Instead of starting at the top and recursing down, start at the bottom and build up. Define dp[i] as the minimum cost to reach step i (including paying cost[i]).

The recurrence:

• dp[0] = cost[0] (start on step 0, pay its cost)
• dp[1] = cost[1] (start on step 1, pay its cost)
• dp[i] = cost[i] + min(dp[i-1], dp[i-2]) for i >= 2

The answer is min(dp[n-1], dp[n-2]), because you can reach the top from either of the last two steps.

def min_cost_climbing_stairs(cost):
    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])

Time: O(n). One pass through the array.

Space: O(n). The dp array.

Let's trace through this for cost = [10, 15, 20]:

The cheapest route is to start on step 1 (pay 15) and jump two steps straight to the top. Total cost: 15. That beats starting on step 0 (pay 10), then stepping to step 2 (pay 20), which totals 30.

Space optimization to O(1)

Look at the recurrence again: dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Each value depends on only the two values before it. You do not need the entire array. Two variables are enough.

def min_cost_climbing_stairs(cost):
    n = len(cost)
    prev2 = cost[0]
    prev1 = cost[1]

    for i in range(2, n):
        current = cost[i] + min(prev1, prev2)
        prev2 = prev1
        prev1 = current

    return min(prev1, prev2)

Same O(n) time, but now O(1) space. Two variables sliding through the array, always holding just enough state for the next calculation.

Let's trace through cost = [10, 15, 20]:

• Start: prev2 = 10, prev1 = 15
• i=2: current = 20 + min(15, 10) = 30. Shift: prev2 = 15, prev1 = 30
• Return min(30, 15) = 15

Complexity analysis

The progression follows the standard DP pipeline:

1. Write the recursive solution to get the logic right.
2. Convert to bottom-up to eliminate recursion overhead.
3. Optimize space by keeping only what the recurrence needs.

You could also add a memoization step between 1 and 2, but for a problem this simple the bottom-up version is just as easy to write directly.

The building blocks

This problem is built on linear DP with constant state, the same pattern as Climbing Stairs and House Robber. You iterate through a sequence, and at each position you compute a value from a fixed number of previous values.

The structure:

• State: dp[i] = minimum cost to reach step i
• Transition: dp[i] = cost[i] + min(dp[i-1], dp[i-2])
• Space optimization: since you only look back two steps, replace the array with two variables

What makes Min Cost Climbing Stairs a great learning problem is that it introduces optimization (choosing the minimum) into a structure you already know from Climbing Stairs. In Climbing Stairs, you add all paths. Here, you select the cheapest. That single difference is the key idea behind every DP optimization problem.

The same building block shows up in:

• House Robber (LeetCode 198): dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Same two-variable lookback, but maximizing instead of minimizing.
• Decode Ways (LeetCode 91): count valid decodings using the previous two DP values.
• Paint House (LeetCode 256): minimize cost with a constraint on adjacent choices, extending the same linear DP idea.

Edge cases to watch for

• Two elements: cost = [10, 15]. You start on step 0 or step 1 and jump to the top. Answer: min(10, 15) = 10.
• Equal costs: cost = [5, 5, 5, 5]. Multiple paths tie. The algorithm picks one automatically since min handles ties.
• Decreasing costs: cost = [100, 50, 10]. Best to start on step 1 (15 cost? No, start step 1 = 50, jump +2 = top, cost 50. Or step 0 = 100, step 2 = 10, cost 110. Or step 1 = 50, step 2 = 60, pick 50). The greedy instinct to "start at the cheapest" does not always work. DP handles all paths correctly.
• Large arrays: the O(1) space solution handles the LeetCode constraint of n <= 1000 instantly.

From understanding to recall

You have read through the recursive approach, the bottom-up DP table, and the space-optimized two-variable version. The pattern probably feels clear right now. But will you be able to write the recurrence and base cases from scratch next week?

Understanding a solution and being able to reproduce it under pressure are different skills. Spaced repetition bridges that gap. You revisit the min-cost recurrence at increasing intervals, write it fresh each time, and after a few reps the pattern becomes automatic. No more second-guessing whether you should take min or max, or which two values to compare at the end.

The constant-state linear DP pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding problems randomly and hoping the patterns stick.

Related posts

• Climbing Stairs - The foundation problem for this one, same staircase without costs
• Coin Change - The next level of DP optimization, where the number of choices varies at each step
• House Robber - Same two-variable lookback with a rob-or-skip decision instead of a min-cost decision