Min Cost Climbing Stairs

Define dp[i] as the minimum cost to reach step i (not the cost of standing on it). You can arrive at step i from i-1 or i-2, and either way you had to pay whatever that previous step cost to leave it. So dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]), with dp[0] = dp[1] = 0 since you can start at either step for free. The answer is dp[n], the cost to reach just past the last step.

Brute Force Recursion

Time O(2ⁿ)Space O(n)

Recurse forward: from step i, either pay cost[i] and jump 1, or pay cost[i] and jump 2. Take the cheaper branch, with the recursion bottoming out once i reaches or passes the top.

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

Every call branches into two more calls, so the tree of recursive calls doubles in size with depth, giving O(2ⁿ) time despite massive overlap between subproblems (the same minCost(i) gets recomputed from many different paths).

Top-Down Memoization

Time O(n)Space O(n)

Cache minCost(i) the first time it’s computed. There are only n distinct values of i, so once each is solved once, every later call is an O(1) lookup.

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

O(n) distinct subproblems, each doing O(1) work beyond its (memoized) recursive calls → O(n) time. The memo dict and recursion depth both cost O(n) space.

Bottom-Up DP

OptimalTime O(n)Space O(n)

Flip the recursion into a forward fill: dp[i] is the minimum cost to arrive at step i, computed left to right. dp[0] = dp[1] = 0 (free starting points), then dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]) for i from 2 to n.

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        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]

Trace for cost = [10, 15, 20] (n = 3):

1 / 3

comparingseenresult

Base cases: dp[0]=0 and dp[1]=0 -- starting at step 0 or step 1 is free, since you have not paid to leave any step yet.

One pass from 2 to n, constant work per step → O(n) time. The full dp array costs O(n) space here, but since each dp[i] only depends on the previous two entries, it can be shrunk to two rolling variables for O(1) space if desired.