Min Cost Climbing Stairs

Same staircase, but now each stair has a price. You may start on stair 0 or stair 1, and each move climbs 1 or 2 stairs. What is the cheapest total cost to reach the top?

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

The same two routes into each stair, but now you keep the cheaper one instead of adding both.

See it build

cost = [10, 15, 20, 5, 25] → cheapest total 20 to the top.

The Problem

One idea changes: add becomes choose

In Climbing Stairs you added the two routes into a stair, because you were counting how many there were. Here you are not counting routes, you are paying for one. So instead of adding the two routes, you keep the cheaper one.

What dp[i] means, in words

dp[i] is the cheapest total cost to reach stair i. Notice the meaning changed from a count to a cost, so the base cases change too: starting is free, so dp[0] = 0 and dp[1] = 0.

The cost row

Each dashed box on top is the price of a stair. You pay that price when you step off the stair toward the next one, so a stair you never use costs nothing.

The top

The goal is one position past the last stair. It has no price of its own, so its value is just the cheapest way to arrive there.

The Key Idea

Two routes in, keep the cheaper

To reach a stair, you arrive either from the stair one below (paying that stair's price) or from two below (paying that stair's price). Both routes are valid, so you compute the total cost of each and keep the smaller. That single word, min, is the whole difference from the last problem.

from one belowdp[i-1] + cost[i-1]

from two belowdp[i-2] + cost[i-2]

→

keep the cheaperdp[i]

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

Try It

Fill the cost row into the answer row

Press play, or step through it. The top row is the fixed cost of each stair. The bottom row is what we compute: the cheapest total to reach that stair. Watch which of the two routes wins at each step.

Press play to start filling the answer row

Press play or step forward to begin.

The amber ring marks the route from one stair below; the teal ring marks the route from two stairs below. The filled cell is the cheaper of the two.

The Result

The filled answer row

For this cost list, the recurrence produces the bottom row below. The last cell, the top, is the answer.

Cheapest total cost to the top: 20.

The Code

Same idea, two implementations

Only two things changed from Climbing Stairs: the base cases start at 0, and the plus became a min over the two priced routes.

Complexity

What the optimization actually buys you

Array

TimeO(n)

SpaceO(n)

Two variables

TimeO(n)

SpaceO(1)

Identical costs to Climbing Stairs. The min changes the answer, not the running time.

Pattern To Remember

When each step carries a value and you want the best total, swap the plus for a min or a max over the same previous states.

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

This min-or-max-over-previous-states shape covers a huge share of easy DP. Next on the course: House Robber, where the choice is take this one or skip it.