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

The bounds are small, so any linear solution runs well within limits. The difficulty 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

Take the last move and recurse on the two predecessors.

def minCostClimbingStairs(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.

With n up to 1000, the branching recursion recomputes the same positions exponentially often. The call tree overlaps heavily:

graph TD
    R5["reach(5)"] --> R4["reach(4)"]
    R5 --> R3a["reach(3)"]
    R4 --> R3b["reach(3)"]
    R4 --> R2a["reach(2)"]
    R3a --> R2b["reach(2)"]
    R3a --> R1["reach(1)"]

reach(3) and reach(2) are each computed more than once, and the duplication compounds at larger n. Caching those results is the fix.

Approach 2 — Top-down memoization

Only n + 1 distinct subproblems exist. Cache reach(i) so each is solved once.

from functools import cache

def minCostClimbingStairs(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

Fill reach from index 2 upward so both dependencies already exist.

def minCostClimbingStairs(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)

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

def minCostClimbingStairs(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. Starting from reach(1) = 0, the running prev1 takes the values 0, 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 the recurrence carries a cost and takes a min instead of a count and a sum. Choosing the state as “cost to reach position i” keeps the base cases simple: both free starting stairs collapse to reach = 0. When a 1-D DP only looks a fixed distance back, collapse the table to rolling variables.