Min Cost Climbing Stairs: LeetCode 746 DP Walkthrough

If you have solved Climbing Stairs (#70), you already know the core idea behind Min Cost Climbing Stairs (#746). Both problems use the same Fibonacci-style recurrence, but the objective flips from counting paths to minimizing cost. Instead of asking "how many ways can you reach the top?", this problem asks "what is the cheapest way to get there?"

That single change — adding a cost array — transforms a pure counting problem into an optimization problem. It is the natural next step in the 1-D dynamic programming progression, and it lays the groundwork for harder problems like House Robber (#198) that extend the same recurrence with adjacency constraints.

In this walkthrough, you will see the min cost climbing stairs leetcode recurrence, how to optimize it to O(1) space, and a visual trace through a concrete example so the logic clicks before you ever open your editor.

You are given an integer array cost where cost[i] is the price you pay to step on stair i. Once you pay that cost, you can climb either one or two steps. You can start from index 0 or index 1, and your goal is to reach past the last stair (index n) with the minimum total cost.

The key insight is that you are stepping past the array. The "top" is not cost[n-1] — it is the position after cost[n-1]. You can land on the top from either of the last two stairs, so the answer considers both ending positions.

This is what makes the leetcode 746 solution slightly tricky for first-timers. The top of the staircase is an implicit position beyond the array, and you must compare the cost of arriving there from step n-1 versus step n-2.

Define dp[i] as the minimum cost to reach stair i (and pay its cost). The recurrence is straightforward: dp[i] = cost[i] + min(dp[i-1], dp[i-2]). At each stair, you pay cost[i] and arrive from whichever of the two previous stairs was cheaper.

The base cases are dp[0] = cost[0] and dp[1] = cost[1]. You can start from either step 0 or step 1, so there is no prior cost to add at these positions. You simply pay the cost of the starting stair.

The final answer is min(dp[n-1], dp[n-2]) — not just dp[n-1]. Since you can reach the top by taking one step from stair n-1 or two steps from stair n-2, you compare both and return the smaller value.

Just like Climbing Stairs, you only need the last two dp values at any point. Replace the entire dp array with two variables — prev2 and prev1 — and update them as you iterate. This drops space from O(n) to O(1) while keeping time at O(n).

Initialize prev2 = cost[0] and prev1 = cost[1]. For each stair from index 2 to n-1, compute current = cost[i] + min(prev1, prev2), then shift: prev2 = prev1, prev1 = current. After the loop, the answer is min(prev1, prev2).

This stairs optimization dp technique is identical to the Fibonacci number space optimization. Once you recognize the pattern — "I only need the last two values" — you can apply it to any linear recurrence that depends on two prior states.

Let us trace through the example cost = [10, 15, 20] step by step. Start with dp[0] = 10 and dp[1] = 15 — these are the base cases since you can begin at either stair.

For stair 2: dp[2] = cost[2] + min(dp[1], dp[0]) = 20 + min(15, 10) = 20 + 10 = 30. You arrive at stair 2 from stair 0 because it is cheaper (cost 10 versus 15).

The answer is min(dp[1], dp[2]) = min(15, 30) = 15. The optimal path is to start at stair 1 (pay 15), then take two steps to the top, skipping stair 2 entirely. Total cost: 15.

The minimum input size is two stairs. When cost has exactly two elements, the answer is simply min(cost[0], cost[1]) — pick the cheaper starting stair and step to the top. No loop is needed.

When all costs are the same, every path has identical cost. The answer is still min(dp[n-1], dp[n-2]), which depends on whether n is even or odd. When costs are strictly decreasing, the greedy approach of always stepping to the next stair might seem optimal, but the recurrence handles it automatically.

Min Cost Climbing Stairs is the simplest weighted Fibonacci DP problem. It bridges counting (Climbing Stairs #70) and constrained optimization (House Robber #198), making it the ideal second problem in the 1-D DP sequence.

The core lesson is that adding weights to a Fibonacci recurrence changes the objective but not the structure. You still depend on two prior states, you still optimize space to O(1), and you still build the answer bottom-up. Recognizing this pattern means you can adapt the same framework to dozens of DP problems.

Practice this pattern with YeetCode flashcards to lock in the recurrence. When you see "minimize cost along a linear sequence with step choices," your brain should immediately reach for dp[i] = cost[i] + min(dp[i-1], dp[i-2]).