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
- 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.
- 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, sobest[0] = best[1] = 0. - Use the last move. You reached step i either from i − 1 (paying
cost[i - 1]) or from i − 2 (payingcost[i - 2]). Take the cheaper:best[i] = min(best[i-1] + cost[i-1], best[i-2] + cost[i-2]). - 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 stepIn 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
| Approach | Time | Space |
|---|---|---|
| Brute force | O(1.6^n): two calls per call, steps are re-priced many times | O(n): recursion depth |
| Table (shown code) | O(n): one min of two sums per step | O(n): the best list (two variables are enough for O(1)) |
Edge cases
- Two steps (
[5, 5]): returns5. You start on either step and one move reaches the top. - All zeros (
[0, 0]): returns0. - Example
[10, 15, 20]: returns15. 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]: returns6. - One step (
[7]): the constraints guarantee at least two, but the code returns0(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]orbest[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.
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.
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?
The cheapest way to reach tile i is built from the cheapest ways to reach i − 1 and i − 2, so a table works in O(n). Greedy ignores later tolls, sorting loses the order of the tiles, and BFS minimises moves, not cost.
2. The shown code takes O(n) time and O(n) space. What lets you reduce the space to O(1)?
Each new value needs just the previous two, so older entries can be dropped. Saying best[n] alone is enough is wrong because best[n] itself needs the two entries below it, and sorting or skipping steps would change the answer.
3. With cost = [5, 5], what does the shown code return?
best is [0, 0, 0], and best[2] = min(best[1] + cost[1], best[0] + cost[0]) = 5. You start on either step, pay 5 once to leave it, and are past the top. Paying both steps (10) is never needed.
Score 60% or more and the lesson is marked complete.