You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.
You can either start from the step with index 0, or the step with index 1.
Return the minimum cost to reach the top of the floor.
LeetCode Solutions2 <= cost.length <= 10000 <= cost[i] <= 999Each step from 0 to n-1 is computed exactly once and memoized, so the total number of function calls is .
The memo dictionary stores up to n entries, and the recursion call stack can reach a depth of n in the worst case.
This solution uses top-down dynamic programming with memoization, computing the minimum cost to reach and depart from each step recursively from the end of the array. The dfs(i) function returns the minimum cost starting at step i, caching results in memo to avoid recomputing overlapping subproblems. The recurrence cost[i] + min(dfs(i-1), dfs(i-2)) reflects that step i can only be reached from step i-1 or i-2, so we pay cost[i] and choose the cheaper predecessor. Since we can start at either of the last two steps, we return min(dfs(n-1), dfs(n-2)).
Each of the n steps is evaluated once and stored in memo, so no step is recomputed regardless of call order.
The memoization dictionary holds up to n entries, and the recursion stack can grow to depth n in the worst case.
This solution applies top-down memoization in the forward direction, where dfs(i) returns the minimum total cost to climb to the top when starting from step i. The base case i >= len(cost) returns 0 because we have already reached or passed the top. The recurrence cost[i] + min(dfs(i+1), dfs(i+2)) means we pay to leave step i, then choose whichever of the next one or two steps leads to the cheaper overall path. Since we can start from index 0 or 1, we return min(dfs(0), dfs(1)).
The loop runs once from index 2 to n-1, visiting each step exactly once.
A dp array of length n is allocated to store the minimum departure cost for each step.
This solution builds the DP table iteratively from left to right, where dp[i] represents the minimum cost to depart from step i. The base cases are dp[0] = cost[0] and dp[1] = cost[1], and each subsequent entry follows the recurrence dp[i] = cost[i] + min(dp[i-1], dp[i-2]), meaning the cheapest way to depart step i is to pay cost[i] plus the cheaper of arriving from step i-1 or i-2. Since reaching the top requires departing from one of the last two steps, the answer is min(dp[-1], dp[-2]).
The loop iterates from 2 to n, filling each of the n-1 entries once.
A dp array of size n+1 is used to store the minimum arrival cost at each position.
This solution reframes the DP state as the minimum cost to arrive at each position, using a dp array of size n+1 where dp[n] represents reaching the top. Since we can start from step 0 or 1 for free, dp[0] = dp[1] = 0. For each position i from 2 to n, the recurrence dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]) considers arriving via a one-step climb (paying the previous step's cost) or a two-step climb (paying the step two back). The answer is simply dp[n].
The loop runs from 2 to n, performing a constant-time update at each step.
Only two variables are maintained regardless of input size, replacing the DP array entirely.
This solution is a space-optimized version of Solution 4, observing that each step's arrival cost only depends on the two immediately preceding values. Instead of maintaining a full dp array, just two variables prev and curr are kept, both initialized to 0 (representing the free start from position 0 or 1). Each iteration slides the window forward, updating prev and curr to reflect the minimum arrival cost at the next position. After n iterations curr holds dp[n], the minimum cost to reach the top.
A single pass through the array updates each of the n-2 entries in constant time.
No auxiliary data structures are used; the DP state is stored in-place by modifying the input array directly.
This solution eliminates the need for any auxiliary array by accumulating the DP result directly into the cost array. For each index i from 2 onward, cost[i] is incremented by the minimum of the two preceding values, which already hold the total minimum departure cost for their respective steps. Since each entry only looks back at already-updated positions, no data is lost, and the answer is min(cost[-1], cost[-2]) — the cheaper of the two last steps to depart from.
The loop iterates from index 2 to n-1, performing a fixed number of operations per step.
Only two scalar variables are maintained, with no allocation that grows with the input size.
This solution is a space-optimized variant of Solution 3, using two explicitly named variables prev_step1 and prev_step2 instead of a full DP array. Initialized to the departure costs of step 1 and step 0 respectively, each iteration computes the minimum departure cost of the current step and shifts the window forward by reassigning both variables. After the loop, prev_step1 and prev_step2 hold the departure costs of the last two steps, and the answer is their minimum.
| Approach | Rating | Time Complexity | Space Complexity | Advantages | Disadvantages |
|---|---|---|---|---|---|
| Top-Down DP (Memoization, Backward) | Intuitive recursive structure; only computes needed subproblems | stack overhead limits practical use on large inputs | |||
| Top-Down DP (Memoization, Forward) | Forward-thinking direction with a clean top-out base case | stack overhead with no practical advantage over Solution 1 | |||
| Bottom-Up DP (Tabulation) | No recursion overhead; straightforward tabulation | Allocates an array that is unnecessary | |||
| Bottom-Up DP (Arrival Cost Perspective) | Clean single answer at dp[n]; eliminates the final min() comparison | Slightly larger array with a less common DP framing | |||
| Bottom-Up DP (Space-Optimized, Two Variables) | Optimal space with a concise simultaneous-assignment update | Generic variable names prev/curr are slightly less descriptive | |||
| In-Place DP (Input Mutation) | space with no extra variables; shortest code | Mutates the input array, which may cause issues if the caller reuses it | |||
| Bottom-Up DP (Space-Optimized, Named Variables) | Optimal space with descriptive variable names that enhance readability | Slightly more verbose than Solution 5 |
Both Solution 5: Bottom-Up DP (Space-Optimized, Two Variables) and Solution 7: Bottom-Up DP (Space-Optimized, Named Variables) are optimal, both achieving time complexity and space complexity. Solution 5 is more concise with a single simultaneous-assignment update, while Solution 7 uses descriptive variable names that make the sliding window logic explicit — prefer Solution 5 for brevity and Solution 7 when readability is the priority.
class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: memo = {} # A dictionary to store the minimum cost to reach each step, to avoid redundant calculations
def dfs(i: int) -> int: if i in memo: return memo[i]
if i < 2: return cost[i]
# The cost to reach step i is the cost of step i plus the minimum cost to reach either step i-1 or step i-2 memo[i] = cost[i] + min(dfs(i - 1), dfs(i - 2))
return memo[i]
# We can start from either the last step or the second to last step, so we take the minimum of both return min(dfs(len(cost) - 1), dfs(len(cost) - 2))class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: memo = {} # A dictionary to store the minimum cost to reach each step, to avoid redundant calculations
def dfs(i: int) -> int: if i in memo: return memo[i]
if i >= len(cost): return 0
# The cost to reach step i is the cost of step i plus the minimum cost to reach either step i+1 or step i+2 memo[i] = cost[i] + min(dfs(i + 1), dfs(i + 2))
return memo[i]
# We can start from either step 0 or step 1, so we take the minimum of the two starting points return min(dfs(0), dfs(1))class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: dp = [0] * len(cost) dp[0] = cost[0] dp[1] = cost[1]
# Build the dp array where dp[i] represents the minimum cost to reach step i for i in range(2, len(cost)): dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])
# The answer will be the minimum cost to reach either of the last two steps, since we can climb either one or two steps at a time. return min(dp[-1], dp[-2])class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: n = len(cost) dp = [0] * (n + 1) # dp[i] will hold the minimum cost to reach step i
# We start from step 2 because we can start from either step 0 or step 1 without any cost for i in range(2, n + 1 ): # To reach step i, we can come from step i-1 or step i-2. We take the minimum cost of those two paths and add the cost of the current step. dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
# The answer will be the minimum cost to reach either of the last two steps, since we can climb either one or two steps at a time. return dp[n]class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: # The cost of reaching the current step is the minimum of the cost of reaching the previous step plus the cost of stepping on it, and the cost of reaching the step before that plus the cost of stepping on it. prev, curr = 0, 0
for i in range(2, len(cost) + 1): # Update the cost of reaching the current step and the previous step for the next iteration. prev, curr = curr, min(curr + cost[i - 1], prev + cost[i - 2])
# The minimum cost to reach the top of the stairs is the cost of reaching the last step or the second to last step, whichever is cheaper. return currclass Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: for i in range(2, len(cost)): # The cost of reaching the current step is the minimum of the cost of reaching the previous step plus the cost of stepping on it, and the cost of reaching the step before that plus the cost of stepping on it. cost[i] += min(cost[i - 1], cost[i - 2])
# The minimum cost to reach the top of the stairs is the cost of reaching the last step or the second to last step, whichever is cheaper. return min(cost[-1], cost[-2])class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: # The cost of reaching the current step is the minimum of the cost of reaching the previous step plus the cost of stepping on it, and the cost of reaching the step before that plus the cost of stepping on it. prev_step1, prev_step2 = cost[1], cost[0]
for i in range(2, len(cost)): # Update the cost of reaching the current step and the previous steps for the next iteration. current = cost[i] + min(prev_step1, prev_step2) prev_step1, prev_step2 = current, prev_step1
# The minimum cost to reach the top of the stairs is the cost of reaching the last step or the second to last step, whichever is cheaper. return min(prev_step1, prev_step2)