Leetcode #33: Climbing Stairs

Imagine you are heading up the stairs to your office every morning.

Your building has n steps to reach your floor.

Now, you are a little quirky. You never climb one step at a time if you can help it, but you also never jump more than two steps at a time because — well, your knees are not what they used to be.

So every morning, you ask yourself:

“How many different ways can I get to the top?”

Some days you go 1, 1, 1, 1… Some days you go 2, 2, 2… Some days you mix it up: 1, 2, 1, 2…

That curiosity — counting all the distinct ways to reach the top — is exactly what this problem is about.

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?

Input:

n = 5

Output:

8

Understanding the Core Idea

Let us think about it from the destination backwards.

If you are standing at the step n, You got there from either:

• Step n - 1 (by taking 1 step), or
• Step n - 2 (by taking 2 steps)

So the number of ways to reach the step n is:

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

Does this formula look familiar?

It is the Fibonacci sequence.

Let us verify with small values:

1 Step -> 1 Way to Climb

2 Steps -> 2 Ways to Climb ( 1+1 or 2)

3 Steps -> 3 Ways to Climb ( 1+1+1 or 1+2 or 2+1)

4 Steps -> 5 ways to Climb

(1 + 1 + 1 + 1 or 1 + 1 + 2 or 1 + 2 + 1 or 2 + 1 + 1 or 2 + 2)

5 Steps -> 8 Ways to Climb

f(5) = f(4) + f(3) = 5 + 3 = 8

Why it become Fibonacci

Notice the sequence:

Steps: 1  2  3  4  5  6  7
Ways : 1  2  3  5  8 13 21

Each number is the sum of the previous two:

3 = 2 + 1
5 = 3 + 2
8 = 5 + 3
13 = 8 + 5

So the climbing-stairs problem is essentially the Fibonacci sequence shifted by one position:

0, 1, 1, 2, 3, 5, 8, 13, ...

That’s why solutions to the Climbing Stairs problem often use Fibonacci-style dynamic programming.

Brute Force Approach (Recursion)

The most natural first instinct is to recurse.

At every step, branch into two choices: take 1 step or take 2 steps.

python

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

The Problem:

This recalculates the same subproblems repeatedly.

For example, climbStairs(5) calls climbStairs(4) and climbStairs(3). But climbStairs(4) also calls climbStairs(3).

We compute climbStairs(3) twice — and it gets worse the larger n gets.

Time Complexity: O(2ⁿ) — exponential. Too slow.

Optimal Approach: Dynamic Programming

We can eliminate redundant computation by storing results we have already computed.

Top-Down (Memoization)

python

class Solution:
    def climbStairs(self, n: int) -> int:
        memo = {}

        def dp(i):
            if i <= 2:
                return i
            if i in memo:
                return memo[i]
            memo[i] = dp(i - 1) + dp(i - 2)
            return memo[i]
        return dp(n)

We store each result in a dictionary. If we have already calculated dp(i), we return it immediately without recomputing.

Bottom-Up (Tabulation) — Most Efficient

python

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1

        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

We build the solution from the ground up, starting at the base cases and working our way to n.

Space-Optimised Bottom-Up

Notice that at any step, we only need the last two values — not the entire array.

python

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1

        prev2 = 1  # ways to reach step 1
        prev1 = 2  # ways to reach step 2
        for i in range(3, n + 1):
            curr = prev1 + prev2
            prev2 = prev1
            prev1 = curr
        return prev1

Driver Code:

python

sol = Solution()

print(sol.climbStairs(1))   # Output: 1
print(sol.climbStairs(2))   # Output: 2
print(sol.climbStairs(5))   # Output: 8
print(sol.climbStairs(10))  # Output: 89

Output:

1
2
8
89

The space-optimised approach is the best: O(n) time and O(1) space.

Key Takeaways

• This problem is a disguised Fibonacci sequence.
• The recurrence relation is: ways(n) = ways(n-1) + ways(n-2).
• Brute force recursion is exponentially slow due to overlapping subproblems.
• Dynamic programming eliminates redundancy by caching or building from the bottom.
• The space-optimised solution needs only two variables at any point.
• This is one of the most classic entry-level DP problems asked in interviews at companies like Google, Amazon, and Meta.

Read my other solutions with thought process.

Thanks for reading.

— Shruti Mandaokar