Min Cost Climbing Stairs

Problem

You are given an array cost where cost[i] is the price of stepping off stair i. From any stair you may move 1 or 2 stairs upward. You may begin from stair 0 or stair 1 for free (you only pay when you leave a stair).

The “top” is the position just beyond the last stair (index len(cost)). Return the minimum total cost to reach the top.

Examples

• cost = [10, 15, 20] → 15 — start on stair 1, pay 15, take a double step past stair 2 to the top.
• cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] → 6 — start on stair 0, then repeatedly hop over the 100s, paying 1 six times.
• cost = [0, 0, 0, 1] → 0 — every stair through index 2 is free, and a double step from stair 2 to the top skips the 1 on stair 3 entirely; total 0.

Constraints

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

Small bounds, so any linear approach is instant; the challenge is defining the state and base cases cleanly.

Think about it first

TL;DR

Define reach(i) = min cost to stand on position i; answer is reach(n) computed with two rolling variables — O(n) time, O(1) space.

The recurrence

Let n = len(cost) and let reach(i) be the minimum cost to arrive at position i (positions 0 … n, where n is the top). The move into i came from i-1 (paying cost[i-1] to leave it) or from i-2 (paying cost[i-2]):

reach(i) = min(reach(i-1) + cost[i-1], reach(i-2) + cost[i-2])
reach(0) = 0        # start here for free
reach(1) = 0        # or start here for free
answer   = reach(n)

Approach 1 — Brute-force recursion

Peel off the last move and recurse on the two predecessors.

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

Complexity: O(2^n) time, O(n) stack.

Why the constraints kill it: with n up to 1000 the branching recursion revisits the same positions exponentially often — astronomically slow despite the small array.

Approach 2 — Top-down memoization

The insight: only n + 1 distinct subproblems exist. Cache reach(i) so each is solved once.

from functools import cache

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

Complexity: O(n) time, O(n) space (cache + stack).

Approach 3 — Bottom-up tabulation

The insight: fill reach from index 2 upward so both dependencies already exist.

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]

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

• dp[2] = min(dp[1] + cost[1], dp[0] + cost[0]) = min(0+15, 0+10) = 10
• dp[3] = min(dp[2] + cost[2], dp[1] + cost[1]) = min(10+20, 0+15) = 15

Return dp[3] = 15. ✓

Complexity: O(n) time, O(n) space.

Approach 4 — Space-optimized (rolling variables)

The insight: dp[i] reads only dp[i-1] and dp[i-2], so two scalars suffice.

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

Walkthrough (cost = [1,100,1,1,1,100,1,1,100,1]): the loop keeps choosing the cheaper predecessor, always hopping over the 100s. The running prev1 climbs 0 → 1 → 1 → 2 → 2 → 3 → 3 → 4 → 4 → 5 → 6, ending at 6. ✓

Complexity: O(n) time, O(1) space.

Common pitfalls

• Paying to leave vs. arrive. The clean formulation charges cost[i-1]/cost[i-2] on the move into i. If instead you define the state as “cost to leave stair i,” the base cases and final answer shift — pick one convention and hold it.
• Forgetting the top is index n, not n-1. The goal is beyond the last stair; returning dp[n-1] undercounts the last hop.
• Only allowing a start at stair 0. You may start at stair 0 or 1 for free — both base cases are 0.

Pattern takeaway

Same skeleton as Climbing Stairs, but now the recurrence carries a cost and takes a min instead of a count and a sum. The trick that keeps the base cases painless is choosing the state as “cost to reach position i” so both free starting stairs collapse to reach = 0. When a 1-D DP only looks a fixed distance back, always finish by collapsing the table to rolling variables.