Min Cost Climbing Stairs: Climbing Stairs with a price tag

The previous article in this series walked through Climbing Stairs. The recurrence there was dp[i] = dp[i+1] + dp[i+2] — the number of ways to reach the top from step i equals the sum of ways from the next two steps.

Min Cost Climbing Stairs adds exactly one thing: each step has a cost. You pay it when you leave that step. The recurrence becomes dp[i] = cost[i] + min(dp[i+1], dp[i+2]). You add cost instead of counting paths, and you take min instead of +. Same skeleton, different combiner. The pattern has a name: two-lookback DP. The optimal answer at any position depends on the optimal answers at exactly the next two positions, nothing further back, nothing forward.

The problem

Given an integer array cost where cost[i] is the cost of the ith step on a staircase, you pay that cost when you leave the step and may then climb one or two steps. You can start from step 0 or step 1, and the goal is to reach the top — the position just past the last index — at minimum total cost. Full statement: LeetCode 746.

Constraints:
- 2 <= cost.length <= 1000
- 0 <= cost[i] <= 999

The problem and what the constraints actually force

You are given an integer array cost where cost[i] is the price of the ith step. Once you pay it, you can climb one or two steps. You may start from index 0 or index 1. Return the minimum cost to reach the top — the position just past the last rung.

Constraints: 2 <= cost.length <= 1000, 0 <= cost[i] <= 999.

The constraint cost.length <= 1000 matters. It rules out brute-force enumeration of all paths (2^n paths in the worst case, which would be 2^1000 — hopeless), but it comfortably allows O(n) and O(n^2) solutions. An O(n) DP is the natural fit. The non-negativity constraint cost[i] >= 0 means you can never gain cost by visiting a step, so you never want to visit a step twice — which rules out any graph-with-negative-edges concern and keeps the recurrence clean. The small upper bound of 999 per step with at most 1000 steps means total cost fits in a 32-bit int (max ~999,000), no overflow.

cost = [10, 15, 20] — answer is 15. Start at index 1, pay 15, jump two rungs directly to the top.

cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] — answer is 6. Stay off the 100s by jumping two rungs whenever the next two rungs are both cheap.

Recursion and why it's the right starting point

The most natural way to think about this problem is recursive. From any step i, you decide: take one step or two? The cost of that decision is cost[i] plus whatever the optimal path from i+1 (or i+2) costs. Once you are past the last rung, you owe nothing.

Without memoization, minCost(2) gets computed multiple times — once via path 0->1->2 and again via 0->2 and 1->2. Memoization cuts this to O(n) by caching each index once.

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        memo = {}
 
        def min_cost(i: int) -> int:
            if i >= len(cost):
                return 0
            if i in memo:
                return memo[i]
            memo[i] = cost[i] + min(min_cost(i + 1), min_cost(i + 2))
            return memo[i]
 
        return min(min_cost(0), min_cost(1))

public class Solution {
    private Dictionary<int, int> memo = new();
    private int[] cost = null!;
 
    public int MinCostClimbingStairs(int[] cost) {
        this.cost = cost;
        return Math.Min(MinCost(0), MinCost(1));
    }
 
    private int MinCost(int i) {
        if (i >= cost.Length) return 0;
        if (memo.TryGetValue(i, out int cached)) return cached;
        return memo[i] = cost[i] + Math.Min(MinCost(i + 1), MinCost(i + 2));
    }
}

Time: O(n) — each index computed once. Space: O(n) for the memo dictionary and the call stack. With cost.length <= 1000, recursion depth is at most 1000, so no stack overflow concern here. Still, the call overhead and dictionary allocation are unnecessary once you see the bottom-up path.

Bottom-up DP: filling right to left

Flip the direction. Instead of asking "what is the cheapest way from i to the top?", precompute it for every i starting from the last rung.

Define dp[i] as the minimum cost to reach the top starting from step i. Base cases: dp[n] = dp[n+1] = 0 — if you are already at or past the top, you owe nothing. Recurrence: dp[i] = cost[i] + min(dp[i+1], dp[i+2]).

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        n = len(cost)
        dp = [0] * (n + 2)      # dp[n] and dp[n+1] stay 0
 
        for i in range(n - 1, -1, -1):
            dp[i] = cost[i] + min(dp[i + 1], dp[i + 2])
 
        return min(dp[0], dp[1])

public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        int n = cost.Length;
        int[] dp = new int[n + 2];   // dp[n] and dp[n+1] initialised to 0
 
        for (int i = n - 1; i >= 0; i--)
            dp[i] = cost[i] + Math.Min(dp[i + 1], dp[i + 2]);
 
        return Math.Min(dp[0], dp[1]);
    }
}

Walk through cost = [10, 15, 20] step by step:

Start: dp = [0, 0, 0, 0, 0]   (indices 0..4, dp[3] and dp[4] are the two base cases)

i = 2: dp[2] = cost[2] + min(dp[3], dp[4]) = 20 + min(0, 0) = 20
       dp = [0, 0, 20, 0, 0]

i = 1: dp[1] = cost[1] + min(dp[2], dp[3]) = 15 + min(20, 0) = 15
       dp = [0, 15, 20, 0, 0]

i = 0: dp[0] = cost[0] + min(dp[1], dp[2]) = 10 + min(15, 20) = 25
       dp = [25, 15, 20, 0, 0]

Answer: min(dp[0], dp[1]) = min(25, 15) = 15

At step 1, paying 15 and jumping two rungs is cheaper than paying 10 at step 0 and then paying another 15 at step 1 (total 25). The DP captures this without any guessing.

The longer example gives a cleaner picture of what the recurrence actually does. cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]:

i = 9:  dp[9]  = 1   + min(0,    0)   = 1
i = 8:  dp[8]  = 100 + min(1,    0)   = 100
i = 7:  dp[7]  = 1   + min(100,  1)   = 2      <- skips index 8
i = 6:  dp[6]  = 1   + min(2,  100)   = 3      <- skips index 8
i = 5:  dp[5]  = 100 + min(3,    2)   = 102
i = 4:  dp[4]  = 1   + min(102,  3)   = 4      <- skips index 5
i = 3:  dp[3]  = 1   + min(4,  102)   = 5      <- skips index 5
i = 2:  dp[2]  = 1   + min(5,    4)   = 5
i = 1:  dp[1]  = 100 + min(5,    5)   = 105
i = 0:  dp[0]  = 1   + min(105,  5)   = 6      <- skips index 1

Answer: min(dp[0], dp[1]) = min(6, 105) = 6

The DP finds the cheapest path entirely by skipping over each 100-cost step. Notice that index 0 is far better than index 1 as a starting point — the recurrence naturally propagates this.

Time: O(n). Space: O(n).

Space-optimised: two variables

The recurrence only looks back two positions. You never need dp[i+3] or earlier. So the array is overkill — two variables are enough.

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        a, b = 0, 0    # a = dp[i+1], b = dp[i+2]
 
        for i in range(len(cost) - 1, -1, -1):
            a, b = cost[i] + min(a, b), a
 
        return min(a, b)

public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        int a = 0, b = 0;   // a = dp[i+1], b = dp[i+2]
 
        for (int i = cost.Length - 1; i >= 0; i--)
            (a, b) = (cost[i] + Math.Min(a, b), a);
 
        return Math.Min(a, b);
    }
}

O(n) time, O(1) space. The simultaneous assignment matters. When computing the new a, you need the old a as the new b. In Python, tuple unpacking handles this in one expression. In C#, tuple deconstruction does the same. Writing them as two sequential statements would produce the wrong answer because b = a would see the already-updated a.

This is the version I'd ship in an interview. It signals that you understand the recurrence well enough to collapse it — the interviewer can see you are not just memorising the formula.

Complexity across all three approaches

All three reach O(n) time because memoization ensures each index is computed once. The space difference is the only real gap. I'd start with bottom-up DP on a whiteboard (the trace is transparent), then mention the two-variable optimisation.

The starting-index choice is not a special case

return min(dp[0], dp[1]) handles "you may start at index 0 or index 1". It is not an edge case bolted onto the end — it is part of the recurrence boundary. Both are valid starting points with their own cost-to-top values; the answer is whichever is cheaper. Forgetting it and always returning dp[0] produces the wrong answer on cost = [10, 15, 20] (returns 25 instead of 15). Worth testing explicitly.

Edge cases and why the recurrence handles them

Minimum input (cost.length == 2): The only valid starting positions are 0 and 1. From either, you jump two rungs and land at the top. dp[0] = cost[0] + min(dp[1], dp[2]) = cost[0] + min(cost[1], 0) = cost[0] (jumping two from 0 costs nothing extra beyond step 0 itself). Answer is min(cost[0], cost[1]). No special-casing needed — the formula works.

All zeros: Every step is free. dp[i] = 0 + min(0, 0) = 0 for all i. Answer is 0. The recurrence runs cleanly with no branch weirdness.

All the same value v: Every path costs the same. From any starting point, the optimal path takes two-step jumps as much as possible (ceil(n/2) steps * v each). The recurrence still settles on the right value without needing to enumerate paths.

Large value at a single rung: Say cost[5] = 999 and everything else is 1. The DP naturally routes around it by checking min(dp[i+1], dp[i+2]) — if jumping over step 5 saves 998, it will. No special handling required.

All zeros except one rung: The answer might be 0 if you can skip the expensive rung via a two-step jump. The recurrence sees this through the min without you doing anything.

Two-lookback DP as a transferable mental model

The underlying pattern here is simple: the optimal answer at position i depends on the optimal answers at exactly i+1 and i+2. Nowhere else. This two-step lookback appears in several problems:

• The combination function cost[i] + min(...) gives minimum cost (this problem).
• Change it to + and you count paths — that is Climbing Stairs (70).
• Change it to max(nums[i] + dp[i+2], dp[i+1]) and you maximise non-adjacent sums — that is House Robber (198).
• Counting valid decodings where each position looks back 1 or 2 characters — that is Decode Ways (91).

In all of them, the two-variable space optimisation applies directly: when the recurrence only looks back two steps, you never need the full array. Recognise the lookback depth, not the specific combination function, and you can collapse any two-lookback DP to O(1) space.

Series placement

This is the second problem in the patterns series. Climbing Stairs (the first) introduced two-lookback DP in its purest form — a counting recurrence with no weights. This problem adds a cost term and swaps + for min, which converts a counting problem to an optimisation problem without changing the recurrence shape at all.

The next step in the series is House Robber, which introduces a constraint: you cannot pick adjacent elements. The lookback is still two positions, but the recurrence now has two branches — take the current element (skip two) or skip it (advance one). That asymmetry is the new wrinkle House Robber adds.