Climbing Stairs

This one looks like a simple counting puzzle. But the interviewer is not really asking about stairs. They want to see if you can spot a pattern, write the rule behind it, and then make that rule run fast. So if you can see that this follows the same sum-of-the-previous-two pattern as Fibonacci, you are showing them you understand dynamic programming. Dynamic programming means you break a big problem into smaller ones, solve each small one once, and reuse the answers.

🪜 The Problem

You are standing at the bottom of a staircase with n steps. Each time you move, you can climb either 1 step or 2 steps. The question is simple: how many different ways can you reach the top?

Input:  n = 3
Output: 3

The 3 ways are:
  1 + 1 + 1
  1 + 2
  2 + 1

See, the order matters here. Going 1 then 2 is a different way from going 2 then 1. So we count both.

🤔 First Thought: Just Try Every Path

The first idea most people get is to try every possible path. From the bottom, you take 1 step or 2 steps. Then from there you again take 1 or 2. You keep going until you reach the top, and you count every full path that lands exactly on step n.

This works, but it is slow. The same small staircase gets solved again and again. To reach step 5, you solve step 3 many times over. The work roughly doubles with each extra step, so the time blows up quickly. So for a large n, this plain try-everything method becomes too slow to use.

💡 The Better Idea: Find the Pattern

Now think about the very last move you made to reach the top step n. There are only two ways that last move could have happened.

• Your last move was a single step. That means you were standing on step n-1 just before.
• Your last move was a double step. That means you were standing on step n-2 just before.

So every way to reach step n ends with one of those two cases. Nothing else is possible. That gives us a clean rule:

ways(n) = ways(n-1) + ways(n-2)

Look at that rule closely. Each value is the sum of the two values before it. That is exactly the pattern behind the Fibonacci sequence. Fibonacci is a number list where every number is the sum of the two numbers before it. Our series here is 1, 2, 3, 5, 8, which is Fibonacci shifted by one. So climbing stairs follows the same sum-of-the-previous-two rule.

We only need the starting values. There is 1 way to reach step 1 (one single step). There are 2 ways to reach step 2 (1+1 or 2). After that, the rule fills in the rest.

🪜 Steps to Solve It

These steps turn the recurrence into a loop that uses only two variables.

1. If n is 1 or 2, the answer is just n. Return it directly.
2. Keep two variables: prev for ways(n-1) and prevPrev for ways(n-2). Start them at 2 and 1.
3. Loop from step 3 up to step n.
4. In each loop, add the two variables to get the current count.
5. Slide the variables forward: the old prev becomes prevPrev, and the new count becomes prev.
6. After the loop ends, prev holds the answer.

#include <stdio.h>

// Count distinct ways to climb n stairs using O(1) extra space
int climbStairs(int n) {
    if (n <= 2) return n;          // base cases: 1 way for 1, 2 ways for 2
    int prevPrev = 1;              // ways to reach step n-2
    int prev = 2;                  // ways to reach step n-1
    int curr = 0;
    for (int i = 3; i <= n; i++) {
        curr = prev + prevPrev;    // the Fibonacci rule
        prevPrev = prev;           // slide the window forward
        prev = curr;
    }
    return prev;
}

int main(void) {
    printf("%d\n", climbStairs(3));
    printf("%d\n", climbStairs(5));
    return 0;
}

3
8

#include <iostream>
using namespace std;

// Count distinct ways to climb n stairs using O(1) extra space
int climbStairs(int n) {
    if (n <= 2) return n;          // base cases: 1 way for 1, 2 ways for 2
    int prevPrev = 1;              // ways to reach step n-2
    int prev = 2;                  // ways to reach step n-1
    int curr = 0;
    for (int i = 3; i <= n; i++) {
        curr = prev + prevPrev;    // the Fibonacci rule
        prevPrev = prev;           // slide the window forward
        prev = curr;
    }
    return prev;
}

int main() {
    cout << climbStairs(3) << endl;
    cout << climbStairs(5) << endl;
    return 0;
}

3
8

public class ClimbingStairs {

    // Count distinct ways to climb n stairs using O(1) extra space
    static int climbStairs(int n) {
        if (n <= 2) return n;          // base cases: 1 way for 1, 2 ways for 2
        int prevPrev = 1;              // ways to reach step n-2
        int prev = 2;                  // ways to reach step n-1
        int curr = 0;
        for (int i = 3; i <= n; i++) {
            curr = prev + prevPrev;    // the Fibonacci rule
            prevPrev = prev;           // slide the window forward
            prev = curr;
        }
        return prev;
    }

    public static void main(String[] args) {
        System.out.println(climbStairs(3));
        System.out.println(climbStairs(5));
    }
}

3
8

# Count distinct ways to climb n stairs using O(1) extra space
def climb_stairs(n):
    if n <= 2:
        return n               # base cases: 1 way for 1, 2 ways for 2
    prev_prev = 1              # ways to reach step n-2
    prev = 2                   # ways to reach step n-1
    for i in range(3, n + 1):
        curr = prev + prev_prev  # the Fibonacci rule
        prev_prev = prev         # slide the window forward
        prev = curr
    return prev


print(climb_stairs(3))
print(climb_stairs(5))

3
8

// Count distinct ways to climb n stairs using O(1) extra space
function climbStairs(n) {
  if (n <= 2) return n;          // base cases: 1 way for 1, 2 ways for 2
  let prevPrev = 1;              // ways to reach step n-2
  let prev = 2;                  // ways to reach step n-1
  for (let i = 3; i <= n; i++) {
    const curr = prev + prevPrev;  // the Fibonacci rule
    prevPrev = prev;               // slide the window forward
    prev = curr;
  }
  return prev;
}

console.log(climbStairs(3));
console.log(climbStairs(5));

3
8

⏱️ Time and Space Complexity

Here is how the two approaches compare. The space-optimized version is the one you want to write in the interview.

🧩 Key Takeaways

• ✅ The last move to the top came from either step n-1 or step n-2, so ways(n) = ways(n-1) + ways(n-2).
• ✅ That recurrence follows the same sum-of-the-previous-two pattern as Fibonacci (shifted by one), so the same trick solves both.
• ✅ You only ever need the last two counts, so two variables are enough and space drops to O(1).
• ✅ The plain try-every-path method repeats work and runs in O(2^n), which is too slow for large n.
• ✅ The base cases are 1 way for n = 1 and 2 ways for n = 2.

🚀 What’s Next?

• House Robber
• Fibonacci with DP