Min Cost Climbing Stairs

Difficulty: Easy

Problem

A staircase has a fee on each step: you pay cost[i] whenever you leave step i, moving up by either 1 or 2 steps. You can begin on step 0 or step 1 without paying to get there. Return the smallest total fee needed to get past the final step to the top. This is the cost-minimizing cousin of the problem that counts the ways to climb.

Example

Input: cost = [10,15,20]
Output: 15
Explanation: Begin on step 1 at no charge, pay 15 to leave it, and jump 2 steps to land on the top. Beginning on step 0 would cost 10 plus at least one more fee.

Brute-force approach

The naive recursion is taught inside the guided walkthrough: same explosion as Climbing Stairs, same two cures.

Optimal approach

Key insight: Climbing Stairs with money: the last-hop split is identical, but counting's + becomes optimizing's min. Change the combiner, keep the skeleton.

Bottom-up over positions 0..n: each position takes the cheaper of its two possible arrivals (previous stair + its toll, or two back + its toll).

Steps

  1. State: dp[i] = min cost to stand at position i; dp[0] = dp[1] = 0 (free starts)
  2. Transition: dp[i] = min(dp[i−1] + cost[i−1], dp[i−2] + cost[i−2])
  3. Fill left to right up to position n (the top)
  4. dp[n] is the answer; roll to two variables for O(1) space

Time complexity: O(n) · Space complexity: O(1) with rolling variables

Pseudocode

function minCostClimbingStairs(cost):
    n = length(cost)
    prev2 = ____    // dp[0]: free start
    prev1 = ____    // dp[1]: free start
    
    for i in 2 .. n:
        cur = min(prev1 + cost[____],
                  prev2 + cost[____])
        prev2 = prev1
        prev1 = cur
    
    return ____

Hints

  • You may BEGIN on stair 0 or stair 1 without paying. What do their dp values start at?
  • Arriving from stair i−1 pays that stair's toll on departure, which index?
  • The two-hop arrival departs from stair i−2, which toll?
  • After the loop, which variable holds dp[n], the top?

Complexity questions

What are the naive and DP time complexities?

Naive O(2ⁿ) from branch doubling; DP O(n), each position solved once. The same collapse as Climbing Stairs: exponential call tree pruned to one pass over n+1 positions.

Why does O(1) space suffice?

The transition reaches back only 2 slots. Two rolling variables carry everything the future needs. The reach audit from foundations: dp[i] reads dp[i−1] and dp[i−2] only. Older entries are dead weight, let them go.

Climbing Stairs used dp[i−1] + dp[i−2]; this problem uses min(...). What decides the combiner?

The QUESTION TYPE: counting sums disjoint branches; optimizing takes min/max; feasibility ORs them. State and case-split describe the STRUCTURE; the combiner encodes the QUESTION. Internalize this mapping and transitions start writing themselves.

Why is the 'top' modeled as position n (one past the last stair) instead of position n−1?

Because you must step OFF the last stair (or the one before it) to finish. The destination is beyond the stairs, and its dp slot captures that final paid hop. Finishing means leaving the staircase. If the top were n−1, cost[n−1] would never be charged on the final hop. Getting the destination right is half of this problem's difficulty.

Check your understanding of Min Cost Climbing Stairs

When exactly do you pay a stair's cost?

When you step OFF it (hopping 1 or 2). You pay to LEAVE a stair. Standing is free. That's why starting on stair 0 or 1 costs nothing until you push off.

What changes versus Climbing Stairs?

Only the QUESTION: count of ways becomes minimum cost, so the transition's + between branches becomes a MIN over branches. Same staircase, same last-hop split. Counting SUMS the two arrival groups; optimizing takes the MIN of the two arrival costs. The combiner matches the question: a core DP lesson.

What's the state sentence?

dp[i] = the minimum total cost to STAND on position i (with the top counting as position n). Precision first: dp[i] is the cheapest way to be standing at position i, tolls paid so far. The top is position n, one past the last stair, and dp[n] is the answer.

The transition for dp[i]?

dp[i] = min(dp[i−1] + cost[i−1], dp[i−2] + cost[i−2]). Arrive from either stair, paying ITS toll to leave. The last hop left from stair i−1 (pay cost[i−1]) or from stair i−2 (pay cost[i−2]). Each branch = cost-to-stand-there + toll-to-leave. Cheapest arrival wins.

Base cases?

dp[0] = 0 and dp[1] = 0. You may START on either for free. The problem grants free starting position on stair 0 or 1. Standing there has cost 0; their tolls only enter when you hop off (inside the transition).

Related problems

Keep practising