LeetMotion
You are given an array of integers cost where cost[i] is the cost of stepping on floor i. After paying the cost you can move 1 or 2 steps forward. You may start at index 0 or 1 (for free). Return the minimum cost to reach the top (one past the last index).
2 ≤ cost.length ≤ 1000 ≤ cost[i] ≤ 100Define f(i) = minimum total cost to reach the top starting from step i. If you stand on step i, you pay cost[i] once, then choose the cheaper of jumping to i+1 or i+2:
Base cases: f(n) = 0 and f(n+1) = 0 — being at or past the top costs nothing extra. The answer is min(f(0), f(1)) since you can start at either for free.
The backwards sweep is the key insight for the O(1) space solution. Process from right to left — when you compute f(i), the values at i+1 and i+2 are already final. So you can modify the input array in place: cost[i] += min(cost[i+1], cost[i+2]). When done, cost[i] holds f(i).
At each step try both 1-step and 2-step jumps. Return the minimum. Exponential because the same subproblems are recomputed over and over.
def minCostClimbingStairs(self, cost):
def dfs(i):
if i >= len(cost): return 0
return cost[i] + min(dfs(i + 1), dfs(i + 2))
return min(dfs(0), dfs(1))Cache each dfs(i) result. The first call computes it; every subsequent call returns the cached value immediately. Linear time, O(n) extra space for the cache.
def minCostClimbingStairs(self, cost):
memo = [-1] * len(cost)
def dfs(i):
if i >= len(cost): return 0
if memo[i] != -1: return memo[i]
memo[i] = cost[i] + min(dfs(i + 1), dfs(i + 2))
return memo[i]
return min(dfs(0), dfs(1))Build from the base up. dp[i] = min cost to reach the top from step i. Fill right-to-left, then return min(dp[0], dp[1]).
def minCostClimbingStairs(self, cost):
n = len(cost)
dp = [0] * (n + 1)
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]Modify cost[] in place. Walk backwards from len(cost) - 3 to 0. At each index, add the cheaper of the next two values. After one pass, cost[i] equals the minimum total cost starting from step i. Return the smaller of cost[0] and cost[1].
def minCostClimbingStairs(self, cost):
for i in range(len(cost) - 3, -1, -1):
cost[i] += min(cost[i + 1], cost[i + 2])
return min(cost[0], cost[1])len(cost) - 3? The last two elements (cost[n-1] and cost[n-2]) are already final — from either one you can jump directly to the top, so no update is needed. We only update indices that have two valid successors within the array.| Approach | Time | Space | Notes |
|---|---|---|---|
| Recursion | O(2ⁿ) | O(n) | Recomputes subproblems |
| Memoization | O(n) | O(n) | Top-down, O(n) cache |
| Bottom-Up DP | O(n) | O(n) | Clean array, no recursion |
| In-Place (Optimal) | O(n) | O(1) | Modifies input — check if allowed ✓ |
This problem is a variation of Climbing Stairs with costs. Recognise the pattern when:
i, states i+1 and i+2 are already correct.cost[n-1] and cost[n-2] never need updating. From n-1 you jump 1 step to the top. From n-2 you jump 2 steps to the top. In both cases the cost is already just cost[i] — there are no further successors to add. The loop correctly starts at n-3.
If mutating the input is not allowed (interview constraint), keep two variables next1, next2 that hold the costs for i+1 and i+2:
def minCostClimbingStairs(self, cost):
n = len(cost)
next1, next2 = cost[n - 1], cost[n - 2]
for i in range(n - 3, -1, -1):
curr = cost[i] + min(next1, next2)
next2 = next1
next1 = curr
return min(next1, next2)The top is past the last index. You don't land on cost[n-1] and stop — you must step beyond it. In the in-place solution this is handled automatically: a jump from n-1 goes to n (top), and a jump from n-2 also goes to n.
The loop must go right to left. If you go left to right, you overwrite cost[i] before it's been used as a successor for smaller i. Order matters.
Starting at n-2 instead of n-3 causes cost[n-2] to read cost[n] (index out of bounds) or cost[n+1]. Always start at len(cost) - 3.
Return min(cost[0], cost[1]), not just cost[0]. Starting at step 1 is free and may be cheaper.
[10, 15, 20] → 15 (start at 1, jump 2)[1, 100] → 1 (start at 0, jump 2 straight to top — loop is empty for n=2)[0, 0, 0, 0] → 0 (all zero, any path costs 0)[1, 2, 1, 2, 1, 1, 1] → 4Bottom-Up DP: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
Discussion
…