Climbing Stairs Problem Explained

Problem Link

Problem Statement

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example :

Input: n = 2
Output: 2
//Explanation: There are two ways to climb to the top.
//1. 1 step + 1 step
//2. 2 steps

Input: n = 3
Output: 3
//Explanation: There are three ways to climb to the top.
//1. 1 step + 1 step + 1 step
//2. 1 step + 2 steps
//3. 2 steps + 1 step

Before Coding: Think Like a Human

For the previous blog, we have been going through this together the whole white boarding, but at this time, try to push yourself to analyse it.

Problem Understanding:

The "Climbing Stairs" problem is a classic dynamic programming problem. It asks:

You are climbing a staircase. It takes n steps to reach the top. Each time you can climb 1 or 2 steps. In how many distinct ways can you climb to the top?

1. Recursive

In coding, a recursive method (or recursive function) is like a super-optimistic person who keeps trying to solve a problem by repeatedly doing the same thing over and over, but with a twist: they call themselves to solve smaller pieces of the same problem. Imagine you’re standing at the base of a staircase, thinking, "Should I take 1 step or 2 steps?" Then, you immediately ask yourself again, "Hmm, should I take 1 step or 2 steps now?" and so on. This keeps going in a loop, like asking yourself over and over but forgetting what you did last time. It’s like having a conversation with yourself in an endless loop where you never remember your previous answers!

This is exactly like the Fibonacci sequence: each new term depends on the two before it. So, just like in the Fibonacci world, you’re stuck in a recursive loop where every step relies on the previous two, making this approach the perfect fit for a recursive solution.

function climbStairs(n) {
    if n <= 1 return n  //// base case
    return climbStairs(n-1)+climbStairs(n-2) // // recursive case
}
//Below is how its computing 
climbStairs(4) calls climbStairs(3) and climbStairs(2)
  climbStairs(3) calls climbStairs(2) and climbStairs(1)
    climbStairs(2) calls climbStairs(1) and climbStairs(0)
      climbStairs(1) returns 1
      climbStairs(0) returns 0
    climbStairs(2) returns 1 (1 + 0)
  climbStairs(3) returns 2 (1 + 1)
climbStairs(4) returns 3 (2 + 1)

Final result: 2 (from climbStairs(3)) + 1 (from climbStairs(2)) = **3**

Time Complexity: The recursive solution has O(2^n) because it makes multiple calls that overlap.
Space Complexity: The space complexity is O(n), due to the recursion stack
Why not to Use: This is a very direct recursive implementation. It's easy to understand but above is what happens for a small value like fibonacci(4) very slow for large n due to repeated calculations.

I hope its clear because we will level up using recursion & memoization

2. Recursion Memoization (caching)

The first solution works — but let’s be honest, it’s not the brightest. It keeps doing the same thing over and over, like that one friend who keeps telling you the same story because they forgot they already told you.

Enter Memoization.
Memoization is like giving our recursive function a notepad. Every time it figures out the number of ways to climb a certain number of steps, it jots it down. Then, if it’s asked the same question again, it just flips to the page and says, “Oh, I already know that one!”

Technically speaking, memoization is a technique used to optimize recursive algorithms by storing the results of expensive function calls and reusing them when the same inputs occur again. In simpler terms: it’s caching — save now, reuse later. So, how do we implement it?

We create a JavaScript object (a.k.a. a dictionary, hashmap) to store our computed values. I like using a helper function for cleanliness and readability. Could we do it without one? Sure. But clean code is happy code. Let your function do one thing and do it well.

Here’s how it looks:

var climbStairs = function(n) {
    const memo = {} // Object to store computed results
    const helper = (steps)=>{
        if (steps <= 1) return 1;  // Base case
        if memo[steps] return memo[steps]//// If the value is already in memo, return it immediately

        //// Otherwise, calculate and store the result in memo
        memo[steps] = helper(steps - 1) + helper(steps - 2);
        return memo[steps]; 
    }
     return memo[steps];  // Return the computed result
};

Time Complexity: O(n) – Each value from 0 to n is computed once. Thanks to our memo object, we avoid repeating ourselves.
Space Complexity: O(n) – Due to the recursion call stack, we can go up to n levels deep in the worst case (plus the memo object size).
Why not to Use: Much faster than plain recursion, but you still use recursion, so you’re dealing with call stack depth. For very large n, this can still be a concern (hello, stack overflow).

3. Optimal Approach: Iterative (Bottom-Up Dynamic Programming)

Okay, now we’re done being dramatic with recursion and memory notebooks. It's time to grow up and write a clean, efficient, no-nonsense solution.This is the chef’s kiss of climbing stairs solutions: bottom-up dynamic programming, but with a twist — we’re going to optimize the space too.Instead of storing every result (like in memoization), we just remember the last two answers — because that’s all we really need. Think of it like this:

To get to step nYou only need to know how many ways there are to get to the step n-1 and n-2.
So... why bother storing everything else? Just keep the last two numbers and move on with your life.

Here’s what it looks like:

var climbStairs = function(n) {
    if (n <= 1) return 1;

    let oneStepBefore = 1;    // Ways to reach (n-1)
    let twoStepsBefore = 1;   // Ways to reach (n-2)
    let result = 0;

    for (let i = 2; i <= n; i++) {
        result = oneStepBefore + twoStepsBefore; // Fibonacci-like logic
        twoStepsBefore = oneStepBefore;          // Shift the window
        oneStepBefore = result; //updating the state for the next iteration of the loop.
    }

    return result;
};

Time Complexity: O(n) – We loop once from 2 to n, so it’s linear time.
Space Complexity: No recursion, no memo objects, just a couple of variables.
Why to Use: Fast. Simple. Scalable. You can calculate the number of ways to climb a staircase with 10,000 steps, and your code won’t even blink.

Final Thoughts

Climbing stairs might seem like a simple task — take a step, then another — but when you break it down algorithmically, it turns into a beautiful little puzzle with layers of insight.We started with Recursion then we leveled up with Memoization Finally, we hit peak optimization with the Bottom-Up Iterative approach:
The grown-up. No wasted memory. No stack overflows. Just clean, linear logic and constant space.

The Big Lesson?

Sometimes solving problems isn’t about brute force or even clever data structures. It’s about recognizing patterns, simplifying where you can, and choosing the right tool for the job.

Whether you're prepping for an interview or just growing as a problem solver, remember this:

It's not just about writing code that works — it's about writing code that works well.

And the more you practice, the more you'll start to see these rhythms and mental models emerge. So keep climbing one step at a time. 🪜💡

Climbing Stairs Leetcode