Algorithm

Min Cost Climbing Stairs

Dynamic Programming Pattern

Min Cost Climbing Stairs

You are given an integer array cost where cost[i] is the price you pay to step off index i. Once you pay for a step, you may move either 1 or 2 indices forward. You may start at index 0 or at index 1, whichever you prefer, and starting costs nothing until you step off. Return the minimum total price to reach the top floor, which is the imaginary position just past the last index (index n).

CONSTRAINTS
  • 2 ≤ cost.length ≤ 1000
  • 0 ≤ cost[i] ≤ 999
  • You may begin at index 0 or index 1
  • The top is position n, one past the final index
EXAMPLE 1
Input: cost = [10, 15, 20]
Output: 15
Begin at index 1 for free, pay 15 to step off it, and that 2-hop lands on position 3, which is the top. No route that starts at index 0 can beat this, because it must pay 10 and then still pay again to finish.
EXAMPLE 2
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
The route pays 1 at index 0, then uses 2-hops to skip over both 100s, paying 1 each at indices 2, 4, 6 and 7, and finishing from index 9 — six payments of 1.
EXAMPLE 3
Input: cost = [0, 0, 0, 0]
Output: 0
Every step is free, so any route costs nothing. Zero costs are legal and must not break the code.
EXAMPLE 4
Input: cost = [5, 5]
Output: 5
The top is position 2. Starting free at index 1 and paying 5 gets you there in one hop. Starting at index 0 and paying 5 works equally well, so the minimum is 5, not 10 — you never have to pay for both.
Is the top the last index of the array, or one position past it?
One position past it. If the array has n entries, you are finished when you land on position n. Confirming this is essential — treating the last index as the goal gives a different, wrong answer on almost every input.
Do I pay for the step I land on, or the step I leave?
The one you leave. Standing anywhere is free; cost[i] is charged the moment you move off index i. This also explains why arriving at the top is free.
Can I really start at index 1 without paying for index 0?
Yes, both index 0 and index 1 are free starting positions. This is why the two base values are both zero rather than cost[0] and cost[1].
Can costs be zero, or negative?
Zero is allowed and is a good case to test. Negative costs are not part of this problem, and it is worth asking, because a negative would reward taking extra steps and make the greedy intuitions people carry around even more wrong.
Read the contract carefully first

You move along an array of steps. From a step you may hop 1 or hop 2 forward. Two details in the rules decide everything, and both trip people up. Read them slowly.

First: you pay for the step you leave, not the step you land on. cost[i] is charged when you step off index i. Just standing on a step is free. Moving is what costs.

Second: the top is not the last index. Say the array has n entries. The valid indices run 0 to n-1. The finish line is position n, one past the end. You never pay to arrive at the top, because there is no cost[n]. This is why you can reach the finish from index n-1 or from index n-2.

Take cost = [10, 15, 20]. The top is position 3. Start at index 1, pay 15, and hop two onto position 3. Total: 15. Any route from index 0 pays 10 right away and still has more to pay, so 15 wins.

We are not asked how many routes exist. We want the cheapest one. So when two ways to arrive meet, we keep the smaller cost, not the sum.

Look backwards from the finish

Stand where you want to end up and ask how you could have got there.

First, find the state. Ask what changes as you move: only one thing, the position you stand on. So the answer is a function of one index. Write f(i).

State Definitionf(i) is the cheapest total price to reach position i. Here i runs from 0 up to n, the top.

To be at position i, your last position was i-1 or i-2. Either way you paid that position's cost to hop. So the two ways of arriving give:

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

Read it slowly. To reach i from i-1, first reach i-1 as cheaply as you can — that is f(i-1) — then pay cost[i-1] to step off it. The cost you add is always the step you leave, exactly as the rules said.

The base cases come from the free-start rule: f(0) = 0 and f(1) = 0. You may begin on either index for free, because you have not stepped off yet. The answer we want is f(n).

The recursive version and why it is too slow
python
def solve(cost):
    n = len(cost)

    def f(i):
        if i == 0 or i == 1: return 0        # free to start on either
        return min(f(i - 1) + cost[i - 1],
                   f(i - 2) + cost[i - 2])

    return f(n)

This is correct, and far too slow. Each call makes two more calls. So the call tree doubles at every level, and the total is about 2ⁿ calls. Yet there are only n+1 truly different questions inside. f(i) gets computed from scratch again and again, even though its answer never changes. With n up to 1000, this would never finish.

Memoise, then tabulate

The fix is a notebook. Before you compute f(i), check the notebook. If it is there, return it. If not, compute it, then write it down before returning:

python
def solve(cost):
    n = len(cost)
    memo = {}

    def f(i):
        if i == 0 or i == 1: return 0
        if i in memo: return memo[i]
        memo[i] = min(f(i - 1) + cost[i - 1],
                      f(i - 2) + cost[i - 2])
        return memo[i]

    return f(n)

And since f(i) only reaches down to i-1 and i-2, we can fill a table from the bottom up. Then every value it needs is ready before we reach it:

python
def solve(cost):
    n = len(cost)
    dp = [0] * (n + 1)
    dp[0] = 0                 # free start
    dp[1] = 0                 # free start
    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]

Note the array has length n+1, not n. The extra slot is the top. Forgetting it is the classic off-by-one bug here. It gives an answer that is quietly too small, because it stops one step short and never warns you.

Two variables are enough

Each step i reads only the two slots right behind it. So keep just two numbers and slide them forward:

python
def solve(cost):
    two_back, one_back = 0, 0        # dp[0], dp[1]
    for i in range(2, len(cost) + 1):
        current = min(one_back + cost[i - 1],
                      two_back + cost[i - 2])
        two_back, one_back = one_back, current
    return one_back

O(N) time, O(1) space.

Worked Example:cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
The top is position 10. Filling dp upward, with dp[0] = dp[1] = 0:
- dp[2] = min(dp[1]+cost[1], dp[0]+cost[0]) = min(0+100, 0+1) = 1
- dp[3] = min(dp[2]+cost[2], dp[1]+cost[1]) = min(1+1, 0+100) = 2
- dp[4] = min(dp[3]+cost[3], dp[2]+cost[2]) = min(2+1, 1+1) = 2
- dp[5] = min(dp[4]+cost[4], dp[3]+cost[3]) = min(2+1, 2+1) = 3
- dp[6] = min(dp[5]+cost[5], dp[4]+cost[4]) = min(3+100, 2+1) = 3
- dp[7] = min(dp[6]+cost[6], dp[5]+cost[5]) = min(3+1, 3+100) = 4
- dp[8] = min(dp[7]+cost[7], dp[6]+cost[6]) = min(4+1, 3+1) = 4
- dp[9] = min(dp[8]+cost[8], dp[7]+cost[7]) = min(4+100, 4+1) = 5
- dp[10] = min(dp[9]+cost[9], dp[8]+cost[8]) = min(5+1, 4+100) = 6

Answer 6. Trace the route it found: it hopped over both 100s by using 2-steps at exactly the right moments.

Why the obvious greedy rule fails

It is tempting to say: at each position, just take the cheaper next hop. That rule breaks the moment a cheap step now forces an expensive step later. Take [1, 100, 1, 1]. A greedy walker at index 0 sees a 1-hop costing 1 and a 2-hop also costing 1, and cannot tell them apart. One of those choices strands it on the 100. The cheapest first move is not always part of the cheapest whole route. That is exactly when greedy reasoning fails and building the table becomes necessary.

Crucial Notethe price belongs to the index you leave, so the term you add is cost[i-1], never cost[i]. Writing dp[i] = min(dp[i-1], dp[i-2]) + cost[i] is the most common wrong answer here. It fails right away at i = n, because cost[n] does not exist.
The takeaway

Notice the one slot that carried all the meaning: what you do with the two branches when they come back. Here we took the minimum, because we wanted the cheapest route. A counting question would add them. A "can it be done at all" question would use or. The state and the choices were simple; the combining operation is what the problem was really testing. When a new problem feels familiar, ask first whether it needs a genuinely new state, or just the same state with a different combining operation. Often the recurrence you know is one word away from the answer.

Exponential Plain Recursion
→
O(N) Time · O(N) Space Memoisation
→
O(N) Time · O(N) Space Tabulation
→
O(N) Time · O(1) Space Two Variables