Min Cost Climbing Stairs

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

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.

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 = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] (n = 10): watch the dp bar fill left to right as each step compares its two predecessor routes and keeps the cheaper one.

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.