DSA Min Cost Climbing Stairs

The problem

Min cost climbing stairs asks for the cheapest price to reach the top of a staircase. Each step charges a fee. A climber pays the fee of each step they stand on.

A move climbs one step or two steps. The climber may start on step 0 or on step 1. The top sits past the last step and charges no fee.

cases = [
    ([10, 15, 20], 15),
    ([1, 100, 1, 1, 1, 100, 1, 1, 100, 1], 6),
    ([10, 15], 10),
    ([5], 5),
]
for cost, expected in cases:
    print("cost", cost, "cheapest:", expected)

On the first staircase the cheap plan starts on step 1. One two-step jump from there reaches the top. The price is just the step 1 fee, 15.

Intuition: always stepping to the cheaper step fails

A greedy climber always moves to the cheaper reachable step. The first staircase already breaks that rule. Step 0 is cheaper than step 1, so greedy starts there.

From step 0 every route onward adds another fee. Starting on the pricier step 1 would have jumped straight to the top. The cheap first step blocks the cheap finish.

cost = [10, 15, 20]
# greedy: start on the cheaper first step, then always take the cheaper reachable step
greedy_total = cost[0]
pos = 0
path = [0]
while pos + 2 < len(cost):
    nxt = pos + 1 if cost[pos + 1] <= cost[pos + 2] else pos + 2
    greedy_total += cost[nxt]
    path.append(nxt)
    pos = nxt
print("greedy path:", path)
print("greedy total:", greedy_total)
print("best plan: start on step 1, jump to the top")
print("best total:", cost[1])

Greedy pays 10 and then 15, for 25 in all. The best plan pays only 15. A locally cheap step is not the same as a cheap route.

Brute force: try every route up

The brute force tries both moves at every step. It climbs one step or two, pays each fee on the way, and keeps the cheapest total that reaches the top.

calls = 0

def brute(cost, pos):
    global calls
    calls += 1
    if pos >= len(cost):
        return 0
    one = cost[pos] + brute(cost, pos + 1)
    two = cost[pos] + brute(cost, pos + 2)
    return min(one, two)

def cheapest(cost):
    return min(brute(cost, 0), brute(cost, 1))

for cost in [[10, 15, 20], [1, 100, 1, 1]]:
    calls = 0
    print("cost", cost, "cheapest:", cheapest(cost), "calls:", calls)

The answers are right. The calls repeat work. The cheapest price from one step is recomputed along many different routes.

That repetition is the cue. Compute the price for each step once, store it, and reuse it.

The optimal solution: the cheapest price to each step

The state is pay(i), the cheapest price to stand on step i. That one sentence defines the table.

The first two prices are just their fees, because the climber may start on either step. Each later price is the step fee plus the cheaper of the two prices before it. The answer is the cheaper of the last two prices, since the top charges nothing.

def min_cost(cost):
    if not cost:
        return 0
    if len(cost) == 1:
        return cost[0]
    pay = [0] * len(cost)
    pay[0] = cost[0]
    pay[1] = cost[1]
    for i in range(2, len(cost)):
        pay[i] = cost[i] + min(pay[i - 1], pay[i - 2])
    return min(pay[-1], pay[-2])

for cost in [[10, 15, 20], [1, 100, 1, 1, 1, 100, 1, 1, 100, 1], [10, 15], [5]]:
    print("cost", cost, "cheapest:", min_cost(cost))

All four cases from section 1 pass. The long staircase answers 6. Its cheap route stands only on steps that charge 1.

Walkthrough: pricing the first staircase

Follow the staircase with fees [10, 15, 20]. Each printed line shows the price table after one step is priced.

cost = [10, 15, 20]
pay = [cost[0], cost[1]]
print("first two steps:", pay)
for i in range(2, len(cost)):
    pay.append(cost[i] + min(pay[i - 1], pay[i - 2]))
    print("after step", i, ":", pay)
print("top:", min(pay[-1], pay[-2]))

Step 2 costs 20 plus the cheaper of 10 and 15. Its price is 30. Standing on step 2 is a bad route to the top.

The top takes the cheaper of the last two prices. That is 15, not 30. The answer is read straight off the table.

Complexity

The table prices each step once with one comparison, so the time is O(n) for n steps.

The table holds one price per step, so the space is O(n), and keeping only the last two prices would cut it to O(1).

calls = 0

def brute(cost, pos):
    global calls
    calls += 1
    if pos >= len(cost):
        return 0
    return cost[pos] + min(brute(cost, pos + 1), brute(cost, pos + 2))

for n in [6, 10, 14]:
    cost = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7][:n]
    calls = 0
    brute(cost, 0)
    print("steps", n, "brute force calls from step 0:", calls, "table steps:", n)

The table steps match the staircase length. The brute force calls multiply. Printed counts make the growth plain.

Edge cases and pitfalls

A cost array of length 1 needs care. There is no second starting step. The only route stands on that step and jumps to the top, so the answer is its fee.

An empty cost array has no steps at all. The climber is already at the top. Its price is 0.

def min_cost(cost):
    if not cost:
        return 0
    if len(cost) == 1:
        return cost[0]
    pay = [0] * len(cost)
    pay[0] = cost[0]
    pay[1] = cost[1]
    for i in range(2, len(cost)):
        pay[i] = cost[i] + min(pay[i - 1], pay[i - 2])
    return min(pay[-1], pay[-2])

print("no steps:", min_cost([]))
print("one step:", min_cost([5]))
print("two steps:", min_cost([4, 9]))
print("free steps:", min_cost([0, 0, 0]))
print("one costly step:", min_cost([1, 100, 1]))

The pitfall is charging for the top. The top is a position past the last step, not a step. Its fee is always zero.

A second pitfall is passing over a step and paying anyway. Only steps stood on charge a fee. A two-step jump skips the middle fee entirely.