← DSA Atlas
Dedicated problem page · #746

Min Cost Climbing Stairs

EasyOne-Dimensional Dynamic ProgrammingMin-cost path with 1-or-2 step transitions1-D DP (bottom-up, O(1) rolling state)
Solve on LeetCode ↗
746
EasyOne-Dimensional Dynamic Programming1-D DP (bottom-up, O(1) rolling state)Min-cost path with 1-or-2 step transitions

Min Cost Climbing Stairs

Given an array cost where cost[i] is the price to step on stair i, you may climb one or two stairs each move and may start at stair 0 or stair 1. Return the minimum total cost to reach the top, which is one step beyond the last stair.

Open official problem prompt ↗
In plain English

Compute the least total toll to climb past the last stair, given you pay a stair's toll only when you step on it and may hop one or two stairs at a time.

Picture it like this

Like a toll road where each booth (stair) charges a fee and you may skip at most one booth per move; you start free at either of the first two booths and want the cheapest route off the end.

Example
Input
cost = [10, 15, 20]
Output
15
Why
Start at index 1 (pay 15) and take two steps to reach the top; total 15, cheaper than starting at index 0.
Constraints
2 <= cost.length <= 10000 <= cost[i] <= 999
Pattern lesson

See the pattern, then code

Min-cost path with 1-or-2 step transitions
Recognition clue

You reach the top from either the last stair or the second-to-last stair, and each stair is reachable from one or two below it. Overlapping subproblems on 'cheapest way to reach step i' signal linear DP.

↗
One-Dimensional Dynamic Programming

Count ways or optimize a result where each state depends on earlier positions.. The cheapest cost to stand at step i is cost[i-1] (if you came from i-1) or cost[i-2] (if you came from i-2), whichever prior position was cheaper to reach. The top is step n, reachable from n-1 or n-2 at no extra cost.

New words, made simpleKnow these before the algorithm
The top
A virtual position at index n = len(cost) that costs nothing to occupy but must be reached.
Transition
From step i you may move to i+1 or i+2, paying that destination stair's cost when it is a real stair.
Rolling variables
Two scalars (prev, curr) replacing the dp array since each state depends only on the previous two.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Recursion without memo

Recomputes overlapping subproblems exponentially; too slow.

Recurse minCost(i) = cost[i] + min(minCost(i-1), minCost(i-2)).

Time O(2^n)Space O(n)
Best choiceBottom-up DP with O(1) state

Linear time, constant space; the canonical solution.

Iterate i from 2 to n keeping the min cost to reach the two previous positions.

Time O(n)Space O(1)
The rule we keep true

Invariant

When the loop is about to process index i, curr holds the minimum cost to reach step i-1 and prev holds the minimum cost to reach step i-2.

Why this is correct

Reasoning

Any path to step i must arrive from i-1 or i-2, so the optimal cost to reach i is the cheaper of those two predecessors plus the toll paid to leave them toward i. By computing positions in increasing order, both predecessors are already optimal, so the recurrence is exact; the top (index n) inherits the same rule.

The algorithm in three movesSay these aloud before coding
1Treat the top as index n (n = len(cost)); its cost to occupy is 0

i=2: min(0+15, 0+10)=10

2Let dp[i] = min cost to reach step i; dp[0] = dp[1] = 0 since you start free at 0 or 1

i=3(top): min(10+20, 0+15)=15

3For i from 2 to n: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

answer 15

4Return dp[n]; collapse dp to two rolling variables for O(1) space

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
s0:100
s1:151
s2:202
top:03
1 · Readcost = [10,15,20], n = 3
2 · AskCost to reach steps 0 and 1?
3 · Update stateprev=0, curr=0
4 · ResultStarting positions are free.
Key takeaway

Reaching the top from stair 1 (pay 15) with a two-step jump beats routing through stair 0.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Seed the base cases

    prev and curr represent the cost to reach the first two positions, both 0 because you may start on either for free.

  2. 2
    Lines 5-6Advance the recurrence

    For each index up to n, the new curr is the cheaper of stepping from one stair back (curr + cost[i-1]) or two back (prev + cost[i-2]); prev shifts to the old curr.

  3. 3
    Lines 7Return the top

    After the loop, curr is the minimum cost to reach index n, the floor beyond the last stair.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Length 2 (e.g. [10,15]) -> answer 10 by starting at step 0 and taking a two-step to the top (you must pay one stair's cost to reach the top)
  • All zeros -> answer 0
  • Ascending costs where a single two-step from index 1 is optimal
  • Uniform costs where the path alternates two-steps to skip half the stairs
!

Common beginner mistakes

  • Off-by-one: the top is index n, not n-1, so the loop must run to n inclusive
  • Paying cost to 'stand on' the top; the top has no toll
  • Returning dp[n-1] (the last stair) instead of dp[n] (the floor above it)
  • Assuming you must start at index 0; index 1 is also a free start
Check your understanding

Why does the loop go up to and including n rather than stopping at n-1?

More in One-Dimensional Dynamic Programming

#198House RobberTake-or-skip linear DP#322Coin ChangeUnbounded knapsack (min coins)#300Longest Increasing SubsequencePatience sorting (tails array)#5Longest Palindromic SubstringExpand around center#32Longest Valid ParenthesesIndex stack with sentinel base#70Climbing StairsFibonacci-style linear DP