Min Cost Climbing Stairs

Min Cost Climbing Stairs is the gentlest possible introduction to bottom-up dynamic programming. There are no fancy data structures — just an array you fill left to right, where each entry is built from the two entries before it.

The slow way first

The brute-force idea is recursion: from the top, ask "did I arrive from the stair below or two below?" and try both, recursing each time. But the same stair gets recomputed over and over, giving an exponential O(2ⁿ) blow-up. The recursion tree overlaps badly — that overlap is the signal to switch to DP.

The question to ask: what is the cheapest cost to reach each stair, one stair at a time? If I already know the answer for the two stairs below me, my own answer is one min away.

The idea: build a dp table

Let dp[i] be the minimum cost to reach stair i. You arrive at i either from i-1 (paying cost[i-1] to leave it) or from 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 free: dp[0] = dp[1] = 0, because you may start on either stair without paying yet. The top is index n, so the answer is dp[n].

The key insight: because we fill dp left to right, the two values we need are always already computed by the time we reach i.

Walk through it

Step through the animation. The top row is cost; the bottom row is dp. We fill dp[0] and dp[1] to 0, then the pointer i moves right. At each cell we compare the two ways to arrive and keep the cheaper. For cost = [10, 15, 20], dp ends as [0, 0, 10, 15], and the last cell 15 is the answer.

Pseudocode

n = number of stairs
make dp of size n+1, all zero      # dp[0] and dp[1] start free
for i from 2 to n:
    arrive_from_one = dp[i-1] + cost[i-1]
    arrive_from_two = dp[i-2] + cost[i-2]
    dp[i] = min(arrive_from_one, arrive_from_two)
return dp[n]                        # cheapest cost to the top

The Python solution

def min_cost_climbing_stairs(cost):
    n = len(cost)
    dp = [0] * (n + 1)
    # dp[0] and dp[1] are free starting points
    for i in range(2, n + 1):
        step1 = dp[i - 1] + cost[i - 1]
        step2 = dp[i - 2] + cost[i - 2]
        dp[i] = min(step1, step2)
    return dp[n]

• dp has n + 1 slots: one per stair plus the top at index n.
• dp[0] and dp[1] stay 0 — starting on either stair is free.
• The loop fills the rest left to right; by the time we reach i, both dp[i-1] and dp[i-2] are known.
• step1 arrives from the stair just below; step2 arrives from two stairs below.
• dp[i] = min(step1, step2) keeps the cheaper route, and dp[n] is the final answer.

Complexity

We do constant work at each of the n stairs, so the fill is O(n) time and O(n) space for the table. (You can shrink space to O(1) by keeping just the last two values instead of the whole array.)

When this pattern shows up

Practice