Min Cost Climbing Stairs

Min Cost Climbing Stairs is a gentle first step into dynamic programming. Dynamic programming is a way to solve a big problem by solving small pieces once and saving their answers. The question looks like a puzzle about stairs. But really it tests if you can spot a smaller version of the same problem hiding inside the big one.

🎯 The Problem

You climb a staircase where each step has a cost, and you reach the top for the smallest total.

• You pay the cost when you stand on a step.
• From a step you can climb one step or two steps at a time.
• You may start from step 0 or from step 1.
• The top is just past the last step.

For costs [10, 15, 20], if you start on step 1 you pay 15, then jump two steps and land past the top. So your total is 15. That is cheaper than starting at step 0.

Input:  cost = [10, 15, 20]
Output: 15

Explanation: Start on step 1, pay 15, then jump two steps to the top.

Here is a slightly bigger example to picture the choices. This diagram shows the steps and the jumps you can take.

🐢 Approach 1: Plain Recursion (Brute Force)

Ask the smallest cost to reach each step by working backward.

The idea:

• To reach a spot, your last move came from one step back or two steps back.
• So the cheapest way to reach a spot is its cost plus the cheaper of those two ways.

How it works:

• A function asks the smallest cost to reach step i.
• To answer, it calls itself for step i-1 and step i-2.
• This is recursion, a function that calls itself on a smaller input.

Why it is weak:

• Step 5 needs step 4 and step 3. But step 4 also needs step 3.
• So step 3 gets computed again and again. These are overlapping subproblems.
• The calls grow like a doubling tree, roughly O(2ⁿ). Too slow.

Here is the plain recursion code:

def min_cost_climbing_stairs(cost):
    def dfs(i):
        if i >= len(cost):
            return 0
        return cost[i] + min(dfs(i + 1), dfs(i + 2))

    return min(dfs(0), dfs(1))

⚡ Approach 2: Memoization (Better)

Solve each step once, then read the saved answer.

The idea:

• The smallest cost to reach a given step never changes.
• So save it the first time you compute it.

How it works:

• Keep an array called memo.
• Before computing step i, check memo and return it if it is there.
• Otherwise compute it, save it, then return it.

Why it is fast:

• Memoization means each step is solved one time only.
• Time drops to O(n).

Here is the memoized recursion:

from functools import lru_cache


def min_cost_climbing_stairs(cost):
    @lru_cache(None)
    def dfs(i):
        if i >= len(cost):
            return 0
        return cost[i] + min(dfs(i + 1), dfs(i + 2))

    return min(dfs(0), dfs(1))

⚡ Approach 3: Bottom-Up Tabulation (Better)

Fill a table from the smallest steps up to the answer.

The idea:

• Make an array dp where dp[i] is the smallest cost to stand on step i.
• dp[0] is cost[0] and dp[1] is cost[1], since you can start on either.

How it works:

• For every later step, dp[i] = cost[i] + min(dp[i-1], dp[i-2]).
• The top is just past the last step.
• So the answer is min(dp[n-1], dp[n-2]).

Why it is fine:

• Tabulation needs no recursion stack, only a loop.
• Each step is filled once, so time is O(n).

This diagram shows the table filling for [10, 15, 20]. Watch each cell use the two cells before it.

🚀 Approach 4: Space-Optimized (Best)

Keep only the two values the table rule actually reads.

The idea:

• To fill step i you only need the two steps right before it.
• You never look further back, so the whole array is wasted memory.

How it works:

• Track prev2 and prev1, the costs of the two most recent steps.
• At each step compute the new cost.
• Then slide the two values forward.

Why it is best:

• Time stays O(n).
• Memory drops to O(1). This is the cleanest version to write in an interview.

Steps to Solve

1. Handle the tiny case. If there are two or fewer steps, the answer is the smaller cost.
2. Set prev2 to cost[0] and prev1 to cost[1].
3. Walk from step 2 to the last step.
4. For each step compute current = cost[i] + min(prev1, prev2).
5. Slide forward. Set prev2 to prev1 and prev1 to current.
6. The answer is min(prev1, prev2), since the top is past the last step.

#include <stdio.h>

int minVal(int a, int b) {
    return a < b ? a : b;
}

int minCostClimbingStairs(int cost[], int n) {
    if (n <= 2) {
        return minVal(cost[0], cost[1]);  // smaller of the two
    }
    int prev2 = cost[0];  // cost to reach step i-2
    int prev1 = cost[1];  // cost to reach step i-1
    for (int i = 2; i < n; i++) {
        int current = cost[i] + minVal(prev1, prev2);
        prev2 = prev1;     // slide the window forward
        prev1 = current;
    }
    return minVal(prev1, prev2);  // top is past the last step
}

int main(void) {
    int cost[] = {10, 15, 20};
    int n = 3;
    printf("%d\n", minCostClimbingStairs(cost, n));
    return 0;
}

15

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minCostClimbingStairs(vector<int>& cost) {
    int n = cost.size();
    if (n <= 2) {
        return min(cost[0], cost[1]);   // smaller of the two
    }
    int prev2 = cost[0];  // cost to reach step i-2
    int prev1 = cost[1];  // cost to reach step i-1
    for (int i = 2; i < n; i++) {
        int current = cost[i] + min(prev1, prev2);
        prev2 = prev1;    // slide the window forward
        prev1 = current;
    }
    return min(prev1, prev2);
}

int main() {
    vector<int> cost = {10, 15, 20};
    cout << minCostClimbingStairs(cost) << endl;
    return 0;
}

15

public class MinCostStairs {
    public static int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        if (n <= 2) {
            return Math.min(cost[0], cost[1]);  // smaller of the two
        }
        int prev2 = cost[0];  // cost to reach step i-2
        int prev1 = cost[1];  // cost to reach step i-1
        for (int i = 2; i < n; i++) {
            int current = cost[i] + Math.min(prev1, prev2);
            prev2 = prev1;    // slide the window forward
            prev1 = current;
        }
        return Math.min(prev1, prev2);
    }

    public static void main(String[] args) {
        int[] cost = { 10, 15, 20 };
        System.out.println(minCostClimbingStairs(cost));
    }
}

15

def min_cost_climbing_stairs(cost):
    n = len(cost)
    if n <= 2:
        return min(cost[0], cost[1])   # smaller of the two
    prev2 = cost[0]   # cost to reach step i-2
    prev1 = cost[1]   # cost to reach step i-1
    for i in range(2, n):
        current = cost[i] + min(prev1, prev2)
        prev2 = prev1                  # slide the window forward
        prev1 = current
    return min(prev1, prev2)           # top is past the last step


cost = [10, 15, 20]
print(min_cost_climbing_stairs(cost))

15

function minCostClimbingStairs(cost) {
  const n = cost.length;
  if (n <= 2) {
    return Math.min(cost[0], cost[1]); // smaller of the two
  }
  let prev2 = cost[0]; // cost to reach step i-2
  let prev1 = cost[1]; // cost to reach step i-1
  for (let i = 2; i < n; i++) {
    const current = cost[i] + Math.min(prev1, prev2);
    prev2 = prev1; // slide the window forward
    prev1 = current;
  }
  return Math.min(prev1, prev2);
}

const cost = [10, 15, 20];
console.log(minCostClimbingStairs(cost));

15

Let us walk through the Python version line by line and see why each piece is there.

def min_cost_climbing_stairs(cost):
    n = len(cost)
    if n <= 2:
        return min(cost[0], cost[1])
    prev2 = cost[0]
    prev1 = cost[1]
    for i in range(2, n):
        current = cost[i] + min(prev1, prev2)
        prev2 = prev1
        prev1 = current
    return min(prev1, prev2)

The line n = len(cost) saves the number of steps so we do not count it again. The check if n <= 2 handles the tiny case. With two or fewer steps you can start on either one and jump straight to the top. So the cheaper start wins.

The lines prev2 = cost[0] and prev1 = cost[1] set up our two memory slots. Here prev2 is the cost to stand two steps back. And prev1 is the cost to stand one step back. These are the only two facts we need going forward.

The loop for i in range(2, n) walks from the third step to the last. The line current = cost[i] + min(prev1, prev2) is the heart of it. To reach step i you came from step i-1 or step i-2. You pick the cheaper way in. Then you add the cost of standing on i.

The two lines prev2 = prev1 and prev1 = current slide our window one step forward. Order matters here. We copy the old prev1 into prev2 first. Then we put the fresh value into prev1. The final min(prev1, prev2) gives the answer. The top sits past the last step. So the last move came from one of the two final steps. We take the cheaper of those.

⏱️ Time and Space Complexity

Plain recursion repeats the same work, so it explodes to O(2ⁿ). Memoization and tabulation each touch every step once, so they run in O(n). The space-optimized version also runs in O(n) time but keeps only two numbers, so its memory drops to O(1).

🧩 Key Takeaways

• ✅ To reach a step, your last move came from one step back or two steps back. Pick the cheaper way in.
• ✅ Plain recursion repeats the same small questions, which are the overlapping subproblems.
• ✅ Memoization saves each answer once, top-down. Tabulation fills a table bottom-up. Both run in O(n).
• ✅ You only ever need the last two values, so you can drop the whole array and keep two numbers.
• ✅ The top is past the last step, so the answer is the cheaper of the final two steps.

🚀 What’s Next?

• House Robber II
• Decode Ways