Min Cost Climbing Stairs
EasyPrompt
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.
Example 1:
Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.Example 2:
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.
Constraints:
2 <= cost.length <= 10000 <= cost[i] <= 999
Approaches
4 approaches with complexity analysis and trade-offs.
This approach directly translates the problem's definition into a recursive function. We define a function that calculates the minimum cost from a given step i to the top. The cost from step i is its own cost plus the minimum of the costs from the two subsequent steps (i+1 and i+2). The final answer is the minimum of starting at step 0 or step 1. This method is simple to understand but suffers from re-calculating the same subproblems multiple times, leading to exponential complexity.
Algorithm
- Define a recursive function, let's call it
solve(i), which calculates the minimum cost to reach the top of the staircase starting from stepi. - The base case for the recursion is when
iis greater than or equal ton(the number of stairs). In this scenario, we are at or past the top, so the cost to proceed is 0. - For any other step
i, the cost iscost[i](the cost to step on stairi) plus the minimum of the costs from the next two possible steps:solve(i+1)andsolve(i+2). The recurrence relation is:solve(i) = cost[i] + min(solve(i+1), solve(i+2)). - The problem states we can start at either step 0 or step 1. Therefore, the final answer is the minimum of the costs calculated by starting from these two positions:
min(solve(0), solve(1)).
Walkthrough
The brute-force recursive approach solves the problem by exploring all possible paths to the top. For each step, it makes two recursive calls, one for taking a single step and one for taking two steps. This creates a binary recursion tree.
For example, to find the cost from step i, we calculate cost[i] + min(solve(i+1), solve(i+2)). This process continues until we reach or pass the top of the staircase (index n), at which point the cost is zero. The main drawback is that the cost for a particular step, solve(k), will be computed every time the path-finding process reaches step k, leading to a massive number of redundant calculations.
class Solution { public int minCostClimbingStairs(int[] cost) { int n = cost.length; return Math.min(solve(cost, 0), solve(cost, 1)); } private int solve(int[] cost, int i) { // Base case: If we are at or past the top, no more cost is incurred. if (i >= cost.length) { return 0; } // Cost from current step is cost[i] plus the minimum cost from the next two steps. int costFromThisStep = cost[i] + Math.min(solve(cost, i + 1), solve(cost, i + 2)); return costFromThisStep; }}Complexity
Time
O(2^n) - For each step, we make two recursive calls. This creates a recursion tree of height `n`, with approximately `2^n` nodes, leading to an exponential number of function calls.
Space
O(n) - The space complexity is determined by the maximum depth of the recursion stack, which can be up to `n` in the worst case.
Trade-offs
Pros
Simple to conceptualize and implement.
Closely follows the mathematical recurrence relation of the problem.
Cons
Extremely inefficient due to exponential time complexity.
Leads to a 'Time Limit Exceeded' error on most platforms for even moderately sized inputs.
This approach, also known as memoization, is a top-down dynamic programming technique. It optimizes the brute-force recursion by caching the results of subproblems. We use an array, often called a memo table, to store the minimum cost calculated for each step. When the function is called for a step, it first checks if the result is already in the table. If so, it returns the cached value; otherwise, it computes the result, stores it in the table, and then returns it. This ensures that each subproblem is solved only once.
Algorithm
- Use the same recursive structure as the brute-force approach.
- Create a memoization array,
memo, of sizen(orn+1) to store the computed results for each step. Initialize this array with a special value (e.g., -1) to indicate that the subproblem has not been solved yet. - In the recursive function
solve(i), before any computation, check ifmemo[i]already contains a valid result. If it does, return the stored value immediately. - If
memo[i]has not been computed, calculate the result using the recurrence:cost[i] + min(solve(i+1), solve(i+2)). - Store this newly computed result in
memo[i]before returning it. - The initial call remains
min(solve(0), solve(1)).
Walkthrough
By adding a memoization table, we avoid the redundant computations that plagued the brute-force approach. Each state solve(i) is computed exactly once. The first time solve(i) is called, its result is calculated and stored. Subsequent calls for the same i will retrieve the result in O(1) time from the memo table, drastically reducing the overall time complexity from exponential to linear.
import java.util.Arrays; class Solution { private int[] memo; public int minCostClimbingStairs(int[] cost) { int n = cost.length; memo = new int[n]; Arrays.fill(memo, -1); // Initialize memo table with -1 return Math.min(solve(cost, 0), solve(cost, 1)); } private int solve(int[] cost, int i) { if (i >= cost.length) { return 0; } // If result is already computed, return it from memo table. if (memo[i] != -1) { return memo[i]; } // Compute, store, and return the result. memo[i] = cost[i] + Math.min(solve(cost, i + 1), solve(cost, i + 2)); return memo[i]; }}Complexity
Time
O(n) - Each subproblem `solve(i)` for `i` from 0 to `n-1` is computed only once. The computation for each state takes constant time.
Space
O(n) - We use an array of size `n` for memoization, and the recursion stack can also go up to depth `n`.
Trade-offs
Pros
Drastically improves time complexity to linear.
Guarantees that each subproblem is solved only once.
Maintains the logical flow of a top-down recursive solution.
Cons
Uses O(n) extra space for the memoization table and the recursion stack.
Can be slightly slower than the iterative bottom-up approach due to function call overhead.
May cause a stack overflow for very large
n(though not an issue with the given constraints).
This is a bottom-up dynamic programming approach. Instead of starting from the top and recurring down, we build the solution from the bottom (the start of the staircase) up to the top. We use a dp array where dp[i] stores the minimum cost to reach step i. We can calculate dp[i] based on the values of previous steps (dp[i-1] and dp[i-2]), effectively building the solution iteratively. This approach avoids recursion and its associated overhead.
Algorithm
- Define a
dparray of sizen + 1, wheredp[i]represents the minimum cost to reach stepi. - The 'top' of the staircase is considered step
n. Our goal is to finddp[n]. - Since we can start at step 0 or step 1 without any preceding cost, we can establish base cases. A clever way to model this is to say the cost to reach the 'floor' before step 0 and step 1 is zero. So,
dp[0] = 0anddp[1] = 0. - Iterate from
i = 2up ton. In each iteration, calculatedp[i]using the recurrence relation:dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). This means the cost to reach stepiis the minimum of two possibilities: coming from stepi-1(and payingcost[i-1]) or coming from stepi-2(and payingcost[i-2]). - After the loop completes,
dp[n]will hold the minimum cost to reach the top.
Walkthrough
The key insight for this DP formulation is to define dp[i] as the minimum cost to reach step i. The final destination is the 'top floor', which we can consider as step n. To reach any step i, we must have come from either step i-1 or i-2. The cost to get to step i would be the cost to get to the previous step plus the cost of that previous step. By iterating from the base cases (dp[0]=0, dp[1]=0), we can fill the dp table up to dp[n], which gives us the final answer.
class Solution { public int minCostClimbingStairs(int[] cost) { int n = cost.length; if (n == 0) return 0; if (n == 1) return cost[0]; int[] dp = new int[n + 1]; // Base cases: cost to reach step 0 and 1 is 0, as we can start there. dp[0] = 0; dp[1] = 0; // Build up the dp table. for (int i = 2; i <= n; i++) { // Cost to reach step i is the minimum of coming from i-1 or i-2. dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); } return dp[n]; }}Complexity
Time
O(n) - We iterate through the costs once in a single loop.
Space
O(n) - An array of size `n + 1` is used to store the DP values.
Trade-offs
Pros
Efficient with O(n) time complexity.
Avoids recursion overhead, making it generally faster in practice than memoization.
The iterative logic can be very clear and easy to debug.
Cons
Uses O(n) space for the DP array, which is not optimal.
This is the most optimized approach, building upon the bottom-up DP solution. We observe that the calculation for the current step's minimum cost only depends on the costs of the two immediately preceding steps. This means we don't need to store the entire DP table. We can use just two variables to keep track of the necessary previous results. As we iterate, we update these two variables, effectively sliding our window of calculation forward. This reduces the space complexity to constant, O(1), while maintaining the linear time complexity.
Algorithm
- This approach optimizes the space of the bottom-up DP solution.
- Notice that to calculate
dp[i], we only needdp[i-1]anddp[i-2]. We don't need the entiredparray. - Initialize two variables to track the costs for the last two steps. Let
two_steps_back_cost = 0(representingdp[0]) andone_step_back_cost = 0(representingdp[1]). - Iterate from
i = 2up ton. - In each iteration, calculate the
current_costto reach stepi:current_cost = min(one_step_back_cost + cost[i-1], two_steps_back_cost + cost[i-2]). - Update the variables for the next iteration:
two_steps_back_costtakes the value ofone_step_back_cost, andone_step_back_costtakes the value ofcurrent_cost. - After the loop,
one_step_back_costwill hold the value ofdp[n], which is the final answer.
Walkthrough
We can think of this as a space-optimized version of the Fibonacci sequence calculation. We only need two previous values to compute the next one. We initialize two variables, two_steps_back_cost and one_step_back_cost, to represent the costs to reach the first two positions (which is 0). Then, we loop from the third position (i=2) to the end. In each step, we calculate the current_cost using the two variables, and then update them for the next iteration. This eliminates the need for an O(n) array, making it the most memory-efficient solution.
class Solution { public int minCostClimbingStairs(int[] cost) { int n = cost.length; // two_steps_back_cost represents the min cost to reach step i-2 int two_steps_back_cost = 0; // one_step_back_cost represents the min cost to reach step i-1 int one_step_back_cost = 0; for (int i = 2; i <= n; i++) { int current_cost = Math.min(one_step_back_cost + cost[i - 1], two_steps_back_cost + cost[i - 2]); two_steps_back_cost = one_step_back_cost; one_step_back_cost = current_cost; } return one_step_back_cost; }}Complexity
Time
O(n) - We iterate through the costs once in a single loop.
Space
O(1) - We only use a few constant variables to store the state, regardless of the input size.
Trade-offs
Pros
Optimal space complexity of O(1).
Optimal time complexity of O(n).
Highly efficient and practical for large inputs.
Cons
The logic with shifting variables might be slightly less intuitive at first glance compared to using a DP array.
Solutions
Solution
class Solution {public int minCostClimbingStairs(int[] cost) { int f = 0, g = 0; for (int i = 2; i <= cost.length; ++i) { int gg = Math.min(f + cost[i - 2], g + cost[i - 1]); f = g; g = gg; } return g; }}function minCostClimbingStairs ( cost ) { const n = cost . length ; const f = Array ( n ). fill ( - 1 ); const dfs = i => { if ( i >= n ) { return 0 ; } if ( f [ i ] < 0 ) { f [ i ] = cost [ i ] + Math . min ( dfs ( i + 1 ), dfs ( i + 2 )); } return f [ i ]; }; return Math . min ( dfs ( 0 ), dfs ( 1 )); }class Solution {public: int minCostClimbingStairs(vector<int> &cost) { int f = 0, g = 0; for (int i = 2; i <= cost.size(); ++i) { int gg = min(f + cost[i - 2], g + cost[i - 1]); f = g; g = gg; } return g; }};class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: f = g = 0 for i in range(2, len(cost) + 1): f, g = g, min(f + cost[i - 2], g + cost[i - 1]) return gVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.