The problem
Step i of a staircase costs cost[i] to leave. From a step you climb one or two steps. You may start on step 0 or step 1.
Return the least total cost to reach the top, just past the last step.
Examples
01
- Input
cost = [10, 15, 20]
- Output
15
02
- Input
cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
- Output
6
Constraints
- 2 ≤ cost.length ≤ 1000
- 0 ≤ cost[i] ≤ 999
The idea
Let reach(i) be the cheapest way to be standing on step i; the top is step n, and reach(0) = reach(1) = 0 since you may start there.
You arrive at step i from i − 1, paying cost[i − 1], or from i − 2, paying cost[i − 2]: reach(i) = min(reach(i − 1) + cost[i − 1], reach(i − 2) + cost[i − 2]). Fill it upwards, keeping only the last two values.
- Time
- O(n)
- Space
- O(1)
Solution · every language run against every case
class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: # reach(i): cheapest way to stand on step i (the top is step n). Steps 0 and 1 are free. # reach(i) = min(reach(i - 1) + cost[i - 1], reach(i - 2) + cost[i - 2]) a = b = 0 # reach(i - 2), reach(i - 1) for i in range(2, len(cost) + 1): a, b = b, min(b + cost[i - 1], a + cost[i - 2]) return b