Min Cost Climbing Stairs

Difficulty: Easy | Acceptance: 68.20% | Paid: No Topics: Array, Dynamic Programming

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.

Examples

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.

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 <= 1000
0 <= cost[i] <= 999

Approach 1: Top-Down Dynamic Programming (Memoization)

Intuition We can view this problem as a recursive decision: at each step, we decide whether to jump 1 or 2 steps. Since we might reach the same step multiple times through different paths, we use memoization to store the minimum cost to reach the top from any given step.

Steps

• Create a helper function dp(i) that returns the minimum cost to reach the top from step i.
• Base case: if i is beyond the last index, the cost is 0.
• Recursive step: the cost to reach the top from i is cost[i] plus the minimum of the cost from i+1 and i+2.
• Use a memoization table (array or hash map) to store results of dp(i) to avoid redundant calculations.
• The answer is the minimum of dp(0) and dp(1) since we can start at either step.

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        memo = {}
        n = len(cost)
        
        def dp(i):
            if i >= n:
                return 0
            if i in memo:
                return memo[i]
            memo[i] = cost[i] + min(dp(i + 1), dp(i + 2))
            return memo[i]
        
        return min(dp(0), dp(1))

Complexity

• Time: O(n) — Each step is calculated only once.
• Space: O(n) — For the recursion stack and memoization array.
• Notes: Intuitive but uses stack space which might lead to stack overflow for very large n (though n <= 1000 here).

Approach 2: Bottom-Up Dynamic Programming (Array)

Intuition Instead of recursion, we build the solution iteratively from the bottom up. We create a dp array where dp[i] represents the minimum cost to reach step i.

Steps

• Initialize a dp array of size n.
• Base cases: dp[0] = cost[0] and dp[1] = cost[1].
• Iterate from i = 2 to n - 1. For each step, dp[i] = cost[i] + min(dp[i-1], dp[i-2]). This means the cost to reach step i is the cost of step i plus the cheaper of the two previous steps.
• To reach the top (index n), we can come from either n-1 or n-2. Return min(dp[n-1], dp[n-2]).

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        n = len(cost)
        if n == 2:
            return min(cost[0], cost[1])
        
        dp = [0] * n
        dp[0] = cost[0]
        dp[1] = cost[1]
        
        for i in range(2, n):
            dp[i] = cost[i] + min(dp[i-1], dp[i-2])
            
        return min(dp[n-1], dp[n-2])

Complexity

• Time: O(n) — Single pass through the array.
• Space: O(n) — To store the dp array.
• Notes: Better than recursion as it avoids stack overflow.

Approach 3: Space Optimized Dynamic Programming

Intuition Notice that to calculate the cost for the current step, we only ever need the cost of the previous two steps. We don’t need to store the entire array.

Steps

• Initialize two variables, prev1 and prev2, to store the costs of the previous two steps (cost[0] and cost[1]).
• Iterate from i = 2 to n - 1.
• Calculate current = cost[i] + min(prev1, prev2).
• Update prev2 to prev1 and prev1 to current for the next iteration.
• After the loop, the minimum cost to reach the top is min(prev1, prev2).

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        a, b = cost[0], cost[1]
        for i in range(2, len(cost)):
            a, b = b, cost[i] + min(a, b)
        return min(a, b)

Complexity

• Time: O(n) — Single pass through the array.
• Space: O(1) — Only two variables are used.
• Notes: Optimal space complexity.

Approach 4: In-Place Modification

Intuition If we are allowed to modify the input array, we can use it as the dp array to save space without using extra variables.

Steps

• Iterate from i = 2 to n - 1.
• Update cost[i] to be cost[i] + min(cost[i-1], cost[i-2]).
• After the loop, the array values represent the cumulative minimum cost to reach that specific step.
• Return min(cost[n-1], cost[n-2]).

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        for i in range(2, len(cost)):
            cost[i] += min(cost[i-1], cost[i-2])
        return min(cost[-1], cost[-2])

Complexity

• Time: O(n) — Single pass through the array.
• Space: O(1) — No extra space used (modifies input in-place).
• Notes: Efficient but destroys the original input array.