Module 23 · Dynamic Programming I: One-Dimensional State

223. Minimum Cost Climbing Stairs

Foundation · Download this solution · All solutions and shared helpers

Problem

Given nonnegative costs for stair indices 0 through n-1, reach position n at minimum cost. You may start at position 0 or 1 for free; when leaving stair i, pay cost[i] and move one or two positions. Empty and singleton lists therefore cost zero because the top can be a free starting position.

Examples

Example 1

min_stair_cost([10,15,20])
=> 15

Start at stair 1, pay 15, and jump to the top.

Example 2

min_stair_cost([])
=> 0

The top is already a free starting position.

Example 3

min_stair_cost([5])
=> 0

Starting at position 1 is starting at the top.

Reveal the worked solution and reasoning

Why this mechanism works

Define dp[i] as the cheapest cost to reach position i before paying to leave it. This makes dp[0]=dp[1]=0. To reach i>=2, either leave i-1 after paying its cost or leave i-2 after paying its cost. The destination top has no fee of its own.

State and boundaries

previous and current are dp[i-2] and dp[i-1] before computing dp[i]. Costs belong to departure stairs.

Protocol

Initialize the free start states to zero.
For each position 2 through n compute min(previous+cost[i-2],current+cost[i-1]).
Roll the states.
Return the cost at position n.

Visualization

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

Python implementation

def min_stair_cost(cost):
    previous = current = 0
    for i in range(2, len(cost) + 1):
        next_cost = min(previous + cost[i - 2], current + cost[i - 1])
        previous, current = current, next_cost
    return current

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

min_stair_cost([10,15,20])

L2 min_stair_cost: previous = current = 0
cost=[10, 15, 20]; previous=0; current=0

L3 min_stair_cost: for i in range(2, len(cost) + 1):
cost=[10, 15, 20]; previous=0; current=0; i=2

L4 min_stair_cost: next_cost = min(previous + cost[i - 2], current + cost[i - 1])
cost=[10, 15, 20]; previous=0; current=0; i=2; next_cost=10

L5 min_stair_cost: previous, current = current, next_cost
cost=[10, 15, 20]; previous=0; current=10; i=2; next_cost=10

L3 min_stair_cost: for i in range(2, len(cost) + 1):
cost=[10, 15, 20]; previous=0; current=10; i=3; next_cost=10

L4 min_stair_cost: next_cost = min(previous + cost[i - 2], current + cost[i - 1])
cost=[10, 15, 20]; previous=0; current=10; i=3; next_cost=15

L5 min_stair_cost: previous, current = current, next_cost
cost=[10, 15, 20]; previous=10; current=15; i=3; next_cost=15

Result: 15. Start at stair 1, pay 15, and jump to the top.

min_stair_cost([])

L2 min_stair_cost: previous = current = 0
cost=[]; previous=0; current=0

Result: 0. The top is already a free starting position.

Why the solution is correct

Every route into i has one of the two allowed departure stairs. Optimal predecessor costs plus their departure fees consider all legal final moves, so the minimum is exact. The ascending order supplies both predecessor answers before use.

Time and space

O(n) time and O(1) auxiliary numeric state.

Common mistakes

Mixing a pay-on-arrival state with pay-on-departure transitions double-charges or omits a stair. The top is position n, outside the cost list.

Reasoning card

State: previous and current are dp[i-2] and dp[i-1] before computing dp[i]. Costs belong to departure stairs.

Invariant: Each DP state is minimum cost to reach its position.

Decision to rehearse: Current cost depends on the cheaper of the prior two reachable states.

Finish: Return the cost at position n

Transfer exercise

Return one cheapest route by retaining which predecessor attained each position's minimum.