LeetCode 746 · 1-D DP

Min Cost Climbing Stairs, explained with a picture

A staircase with a toll on every step.

Easy1-D DP
▶ Watch it step by step

The problem

Each step has a cost you pay when you step off it. You may start on step 0 or step 1, and climb 1 or 2 steps at a time. Find the cheapest way to get past the top step.

Input:  cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6

Picture it

Picture a staircase with a toll booth on every step. Each step is labelled with the cheapest total you could have paid to stand there. To stand on step i you came from i − 1 (and paid its toll) or from i − 2 (and paid its toll), so you pick the cheaper of those two. Expensive steps (100) get skipped by jumping over them.

How to recognise it

  • You want the cheapest total (a minimum), not a count, over a sequence of positions.
  • Each move goes forward by a small fixed amount (1 or 2 steps), so the cost of standing on step i depends on only a few earlier steps.
  • Costs are paid when you leave a step, so the price of a route is the sum of the steps you stepped off.
  • The same sub-question ("what is the cheapest way to stand on step k?") comes up from several later steps.
  • With up to 1,000 steps, trying every route is impossible; a table of best costs, filled left to right, is expected (1-D dynamic programming, DP).

Start with brute force

Try every route. From step i you pay cost[i] and move to i + 1 or i + 2; once you are past the last step you stop. Try both starting steps and take the cheaper.

def min_cost_brute(cost):
    n = len(cost)
    def go(i):                       # cheapest cost to get past the top from step i
        if i >= n:
            return 0
        return cost[i] + min(go(i + 1), go(i + 2))
    return min(go(0), go(1))

Each call makes two more calls, so the time is exponential, about O(1.6^n). With only 45 steps that is already billions of calls, and the limit is 1,000 steps. Space is O(n) for the recursion.

From brute force to the idea

  1. Find the waste. Many different routes arrive at the same step. The brute force prices the remaining journey from that step again for each of them.
  2. Define a table. Let best[i] be the cheapest total you have paid by the time you are standing on step i. Starting on step 0 or step 1 is free, so best[0] = best[1] = 0.
  3. Use the last move. You reached step i either from i − 1 (paying cost[i - 1]) or from i − 2 (paying cost[i - 2]). Take the cheaper: best[i] = min(best[i-1] + cost[i-1], best[i-2] + cost[i-2]).
  4. Read the top. The top is one position past the last step, index n, so the answer is best[n]. The table has n + 1 entries for that reason.

This is the key idea: the cheapest cost to stand on step i comes from the two cheapest costs just below it, plus the price of the step you leave.

The key idea

best[i] = min(best[i − 1] + cost[i − 1], best[i − 2] + cost[i − 2]). O(n).

Python solution

def min_cost_climbing_stairs(cost):
    n = len(cost)
    best = [0] * (n + 1)            # cheapest way to stand on step i
    for i in range(2, n + 1):
        best[i] = min(best[i - 1] + cost[i - 1],   # one step from i-1
                      best[i - 2] + cost[i - 2])   # or two from i-2
    return best[n]                   # the top is just past the last step

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(1.6^n): two calls per call, steps are re-priced many timesO(n): recursion depth
Table (shown code)O(n): one min of two sums per stepO(n): the best list (two variables are enough for O(1))

Edge cases

  • Two steps ([5, 5]): returns 5. You start on either step and one move reaches the top.
  • All zeros ([0, 0]): returns 0.
  • Example [10, 15, 20]: returns 15. Start on step 1, pay 15, jump to the top, skipping both 10 and 20.
  • Longer example [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]: returns 6.
  • One step ([7]): the constraints guarantee at least two, but the code returns 0 (you can start on "step 1", which is already the top).
  • Large input: 1,000 steps cost at most 999 each, so the answer is below 10^6 and fits any integer type.

Common mistakes

  • Returning best[n - 1], which is the cost of standing on the last step, not of getting past it (for [10, 15, 20] it gives 10 instead of 15).
  • Adding cost[i] when you arrive on step i instead of when you leave it, which charges the wrong steps.
  • Setting best[0] or best[1] to their cost: starting is free here.
  • Always stepping onto the cheaper of the next two steps. That greedy choice ignores what lies beyond.
Your turn: jumps of 1, 2 or 3

Same rules (pay cost[i] when you leave step i), but you may now climb 1, 2 or 3 steps, and you may start on step 0, 1 or 2. Assume at least three steps. Find the cheapest cost to get past the top. Describe your approach, then write it if you like.

Compare with our answer

The last move can come from three earlier steps, so take a minimum over three options. Steps 0 to 2 are free starting points.

def min_cost_123(cost):
    n = len(cost)
    best = [0] * (n + 1)             # best[i]: cheapest way to stand on step i
    for i in range(3, n + 1):
        best[i] = min(best[i - s] + cost[i - s] for s in (1, 2, 3))
    return best[n]

min_cost_123([10, 15, 20]) is 10 and min_cost_123([1, 100, 1, 1, 1, 100]) is 2. Time O(n), space O(n).

A strong answer mentions: three free start positions, a minimum over the three previous steps (each plus the cost of the step left), the top at index n, and that the loop starts at 3 so no index goes negative.

Check what stuck

1. A row of n tiles each has a toll, you pay the toll of the tile you step off, and you move 1 or 2 tiles at a time (n up to 1,000). You want the lowest total toll to get past the end. Which approach fits best?

2. The shown code takes O(n) time and O(n) space. What lets you reduce the space to O(1)?

3. With cost = [5, 5], what does the shown code return?

Score 60% or more and the lesson is marked complete.