Min Cost Climbing Stairs

Difficulty: Easy Source: NeetCode

Problem

You are given an integer array cost where cost[i] is the cost of the 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 (one step beyond the last index).

Example 1: Input: cost = [10,15,20] Output: 15

Example 2: Input: cost = [1,100,1,1,1,100,1,1,100,1] Output: 6

Constraints:

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

Prerequisites

Before attempting this problem, you should be comfortable with:

• Dynamic Programming — building optimal solutions from subproblems
• Climbing Stairs — understanding the 1-or-2-step recurrence

1. Brute Force (Recursion with Memoization)

Intuition

Define min_cost(i) as the minimum cost to reach the top starting from step i. From step i you can jump to i+1 or i+2. You pay cost[i] to leave step i. The recursion is: min_cost(i) = cost[i] + min(min_cost(i+1), min_cost(i+2)). The “top” is reached when i >= len(cost).

Algorithm

1. Base case: min_cost(i) = 0 if i >= len(cost).
2. Recursive case: min_cost(i) = cost[i] + min(min_cost(i+1), min_cost(i+2)).
3. Start from both step 0 and step 1, return the minimum.

Solution

def minCostClimbingStairs_memo(cost):
    n = len(cost)
    memo = {}

    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))


print(minCostClimbingStairs_memo([10, 15, 20]))                    # 15
print(minCostClimbingStairs_memo([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))  # 6
print(minCostClimbingStairs_memo([0, 0]))                          # 0

Complexity

• Time: O(n) — each subproblem computed once
• Space: O(n) — memo table and recursion stack

2. Dynamic Programming (Bottom-Up)

Intuition

Build the solution from the top down: starting from the last step, work backwards. dp[i] = minimum cost to reach the top from step i. The recurrence is dp[i] = cost[i] + min(dp[i+1], dp[i+2]). After filling the array, the answer is min(dp[0], dp[1]) since we can start from either.

Like Climbing Stairs, we only need the two most recent values — space can be reduced to O(1).

Algorithm

1. Initialize dp = [0] * (n + 1) where the last two positions are 0 (reaching “top” is free).
2. Fill from i = n-1 down to 0: dp[i] = cost[i] + min(dp[i+1], dp[i+2]).
3. Return min(dp[0], dp[1]).

Solution

def minCostClimbingStairs(cost):
    n = len(cost)
    # dp[i] = min cost to reach top from step i
    # Extend cost by two zeros to represent "beyond the array"
    dp = cost + [0, 0]

    for i in range(n - 1, -1, -1):
        dp[i] = cost[i] + min(dp[i + 1], dp[i + 2])

    return min(dp[0], dp[1])


def minCostClimbingStairs_o1(cost):
    # Space-optimized: only track two future values
    n = len(cost)
    next1, next2 = 0, 0  # cost to reach top from step n and n+1

    for i in range(n - 1, -1, -1):
        curr = cost[i] + min(next1, next2)
        next2 = next1
        next1 = curr

    return min(next1, next2)


print(minCostClimbingStairs([10, 15, 20]))                    # 15
print(minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))  # 6

print(minCostClimbingStairs_o1([10, 15, 20]))                    # 15
print(minCostClimbingStairs_o1([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))  # 6
print(minCostClimbingStairs_o1([0, 0]))                          # 0

Complexity

• Time: O(n) — single pass
• Space: O(1) — two variables (space-optimized version)

Common Pitfalls

Thinking the answer is just dp[0]. You can start from step 0 or step 1. The answer is min(dp[0], dp[1]).

Forgetting that reaching the top is free. The “top” is beyond the last step. Once you jump past the last index, you’ve arrived — no additional cost. Set those boundary values to 0.

Confusing top-down vs bottom-up direction. If you fill the DP array left-to-right, you’d be computing the minimum cost to arrive at step i, which works too — but make sure the recurrence and base cases match your chosen direction.