You are given an array cost where cost[i] is the price of stepping on stair i. After paying for a stair you may climb one or two stairs. You can start on stair 0 or stair 1 for free. Return the minimum total cost to reach the top, which is the position just past the last stair.
- 2 <= cost.length <= 1000
- 0 <= cost[i] <= 999
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force recursion tries a 1-step and a 2-step jump from every stair, which is O(2^n). State: dp[i] = minimum cost to reach position i. Recurrence: dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]), because the last jump came from one or two stairs below and you paid for that stair. Base case: dp[0] = dp[1] = 0 since you may start on either for free. Memo turns the recursion into O(n), the table version fills dp left to right, and because each value uses only the last two, two variables are enough.
Algorithm
- Keep
prev2 = 0(dp[i - 2]) andprev1 = 0(dp[i - 1]). - For
ifrom 2 ton, computecur = min(prev1 + cost[i - 1], prev2 + cost[i - 2]). - Shift:
prev2 = prev1,prev1 = cur. - Return
prev1, the cost to reach positionn(the top).
O(n)Space: O(1)n, not n - 1. Returning dp[n - 1] is the most frequent off-by-one bug here; check it on [10,15,20], where the answer is 15, not 10 or 25.class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: n = len(cost) prev2, prev1 = 0, 0 # dp[i - 2], dp[i - 1] for i in range(2, n + 1): cur = min(prev1 + cost[i - 1], prev2 + cost[i - 2]) prev2, prev1 = prev1, cur return prev1 # dp[n]