Min Cost Climbing Stairs Solution

Problem

You have a staircase where each step carries a cost. Once you pay the cost of a step, you can climb one or two steps up. You can start at step 0 or step 1 for free — find the minimum total cost to reach the top (the floor above all steps).

Input: cost = [10, 15, 20]
Output: 15
Explanation: Start at step 1 (free), pay 15, jump two steps to the top.

Another example showing that greedy fails:

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Hop through the cheap steps (1s), skipping the expensive 100s by taking two-step jumps at the right moments.

Intuition

The cost to reach any position depends only on the two positions just below it — you can arrive from one step back or two steps back. This creates a textbook "overlapping subproblems" structure where the same sub-answers get reused repeatedly. The key realization: you arrive at positions 0 and 1 for free (you choose your starting point), so the answer propagates cleanly forward from those free base cases.

Approach 1 — DP Table

Build a table where each entry stores the minimum cost to reach that position. Positions 0 and 1 cost nothing to reach (free start). Fill the rest forward using the recurrence.

Allocate a min_cost array of length n + 1 (the top is at index n, one past the last step).
Set min_cost[0] = 0 and min_cost[1] = 0 — both starting positions are free.
For each position i from 2 to n, compute min_cost[i] as the cheaper of arriving from one step below (paying cost[i-1]) or two steps below (paying cost[i-2]).
Return min_cost[n].

1from typing import List
2
3class Solution:
4    def minCostClimbingStairs(self, cost: List[int]) -> int:
5        n = len(cost)
6        min_cost = [0] * (n + 1)  # index n is the top floor, past all steps
7        for i in range(2, n + 1):
8            arrive_from_one_below = min_cost[i - 1] + cost[i - 1]
9            arrive_from_two_below = min_cost[i - 2] + cost[i - 2]
10            min_cost[i] = min(arrive_from_one_below, arrive_from_two_below)
11        return min_cost[n]

Time: O(n) — single pass through the cost array.

Space: O(n) — the min_cost table holds one entry per position.

Approach 2 — Space-Optimized DP

Each step only looks two positions back, so there's no need to keep the full table — just the two most recent values.

Initialize two_back = 0 and one_back = 0, representing the free cost to reach positions 0 and 1.
For each position i from 2 to n, compute current from one_back and two_back.
Shift the window: two_back = one_back, then one_back = current.
Return one_back (which holds the cost to reach position n).

1from typing import List
2
3class Solution:
4    def minCostClimbingStairs(self, cost: List[int]) -> int:
5        n = len(cost)
6        two_back, one_back = 0, 0  # min cost to reach positions 0 and 1
7        for i in range(2, n + 1):
8            current = min(
9                one_back + cost[i - 1],   # arrive from one step below
10                two_back + cost[i - 2]    # arrive from two steps below
11            )
12            two_back = one_back  # slide the window forward before overwriting one_back
13            one_back = current
14        return one_back

Time: O(n) — same single pass.

Space: O(1) — only two integers, regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
DP Table	O(n)	O(n)	When you want to inspect the full cost table for debugging or backtracking the path
Space-Optimized DP	O(n)	O(1)	In production — same speed, no extra allocation needed

Common Mistakes

Returning dp[n-1] instead of dp[n] — the top of the staircase is the floor above all steps, at index n. Returning the last step's entry misses the final jump; allocate n+1 entries and return the last one.
Initializing dp[0] = cost[0] — because you can start at step 0 for free, dp[0] should be 0, not cost[0]. The cost is paid when you leave a step, not when you choose it as your starting point.
Off-by-one in cost indexing — writing dp[i] = ... + cost[i] in an (n+1)-length table reads cost[n], which is out of bounds. Since dp[i] represents position i, the step you leave to get there is cost[i-1].
Wrong variable update order in the space-optimized version — assigning two_back = one_back after computing current (instead of before) means two_back already holds the updated value when you try to use it next iteration. Always update two_back first, then one_back.
Greedy fails here — always picking the cheapest next step doesn't minimize total cost. With cost = [1, 100, 1, 1, 100, 1], greedily taking the cheapest available step produces a suboptimal route; the two-step jump lets you skip expensive stairs in ways a greedy scan misses.

Min Cost Climbing Stairs — Solution