What is the brute force approach and complexity for Climbing Stairs?

Recursive ways(i) = ways(i−1) + ways(i−2), with no memory with time complexity O(2^N) and space complexity O(N).

What is the optimal approach and complexity for Climbing Stairs?

Keep only the last two answers in two variables and build up from step 3 with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Climbing Stairs?

Look for key signals in the prompt: "how many ways" indicates The question asks for a count, not the list of moves. Build the count step by step, and do not list the paths.; "climb 1 or 2 steps" indicates The choice at each step only looks back one or two steps, so the answer for step i depends only on steps i − 1 and i − 2.; "reach the top" indicates The top is a fixed target, step n. Fill the answers from the bottom up to n..

Climbing Stairs

Easy·LeetCode #70Basic Anchor

LeetCode

Jump:

30-Second Mental ModelDP 1D — Fibonacci-style (two variables)

Complexity:O(2^N)→O(N)

Key Insight

Step i reads only steps i − 1 and i − 2. So we never need the whole memo: only the last two answers matter. Keep two variables, prev2 (ways to reach step i − 2) and prev1 (ways to reach step i − 1). Each new step is prev1 + prev2, and then both variables move up one step. The space is O(1).

Core Validity Invariant

The count for step i is exactly the count for step i − 1 plus the count for step i − 2, because the last move is either a 1-step or a 2-step.

Problem

A staircase has n steps. You start on the ground, below step 1, and you want to reach step n, the top.

Each move takes you up 1 step or 2 steps. Count the different ways to reach the top.

Two ways are different when their moves are in a different order. For example, 1 + 2 and 2 + 1 are two different ways, even though both reach the top.

Input

An integer n, the number of steps.

Output

One integer: the number of different ways to reach step n.

Example 1

Input: n = 2

Output: 2

Two ways: 1 + 1, or one 2-step. Both reach the top.

Example 2

Input: n = 3

Output: 3

Three ways: 1 + 1 + 1, 1 + 2 and 2 + 1.

Constraints

• 1 ≤ n ≤ 45

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If I am standing on step 5, what was my last move? Could I have come from step 4, or from step 3?
2.
How many ways are there to reach step 1? And to reach step 2?
3.
Do I need the full list of moves, or only how many lists there are?
4.
To find the answer for step 6, which earlier answers do I need? Do I need the answers for all of steps 1 to 4?
5.
The next answer only reads two earlier answers. Could I keep just those two numbers?

Brute force approach

Idea

To count the ways to reach step i, count the ways to reach step i − 1 and the ways to reach step i − 2, then add them. Each of those is the same question for a smaller step, so a recursive function can answer them. The base cases are steps 1 and 2. The method is correct, but the same smaller step is asked for again and again, so the work grows very fast.

Thinking process

1
Take n = 5. The last move was a 1-step from step 4 or a 2-step from step 3. So ways(5) = ways(4) + ways(3).
2
Do the same for step 4: ways(4) = ways(3) + ways(2) = 3 + 2 = 5. Check it by listing: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2. That is five ways.
3
Stop at the base cases: ways(1) = 1 and ways(2) = 2. These are the only steps we can answer without looking further back.
4
Count the calls for n = 5. ways(3) is called twice and ways(2) three times. Nothing is remembered, so every call starts again from scratch.

Visual

Each circle is one call to ways(i), and the small number under it is what the call returns. Blue = the path from the top to the current call. Orange = a call whose answer was already worked out earlier in the walk; a memo would return it at once. Purple = the top call (the answer).

Brute force asks the same steps againn = 5step 1/23

tree

step

▲call

Work

calls: 1
repeat calls: 0
distinct answers: 0

ways(5) needs ways(4) and ways(3)

Call ways(5): it needs ways(4) and ways(3).

Code & Implementation

brute.cpp

class Solution {
public:
    // Number of ways to reach step i. The last move decides it:
    // it was a 1-step from step i-1, or a 2-step from step i-2.
    int ways(int i) {
        if (i <= 2) return i;                    // ways(1) = 1 and ways(2) = 2
        return ways(i - 1) + ways(i - 2);        // no memory: the same step is asked again and again
    }

    int climbStairs(int n) {
        return ways(n);
    }
};

Complexity

Time O(2^N)Space O(N)

Here N is n. Each call makes at most two more calls, so the time is at most 2^N. The call depth is at most n, so the stack uses O(N) space. For n = 5 there are 9 calls, but only 5 different steps, so 4 calls are repeats.

Better approach

Why brute force is slow

The recursion asks for the same step many times. For n = 5, step 2 is answered 3 times and step 3 twice, and each time it starts from scratch.

What repeated work are we doing?

The whole subtree for ways(3) is worked out twice: once under ways(4), and once directly under ways(5). Both times it gives the same answer.

What information can we reuse?

Store ways(i) in memo[i] the first time it is known. The second visit returns the stored number and skips its calls.

New approach

Idea

Keep the same recursion, but write each answer into an array memo the first time it is worked out. When the same step is asked for again, return the stored number. Each step is worked out only once, and every later visit is a lookup.

Thinking process

1
In the n = 5 tree, the brute force works out ways(3) twice. The second time it gets the same answer, 3, which is wasted work.
2
Store it in memo[3] the first time. The next call for step 3 finds memo[3] != -1 and returns 3 at once.
3
Check it on n = 5: ways(3) is solved under ways(4). Under ways(5), the second ways(3) returns 3 from the memo, so its two calls to ways(2) and ways(1) are skipped.
4
The memo has one slot for each step, so each step from 3 to 5 is worked out one time.

Code & Implementation

better.cpp

class Solution {
public:
    int climbStairs(int n) {
        // memo[i] = ways to reach step i, or -1 while it is still unknown.
        vector<int> memo(n + 1, -1);
        return ways(n, memo);
    }

private:
    int ways(int i, vector<int>& memo) {
        if (i <= 2) return i;
        if (memo[i] != -1) return memo[i];       // solved before: reuse it, skip its calls
        memo[i] = ways(i - 1, memo) + ways(i - 2, memo);
        return memo[i];
    }
};

Complexity

Time O(N)Space O(N)

Here N is n. Each step from 3 to n is worked out once, and each later visit is a lookup. The memo array takes O(N) space, and the recursion depth is also O(N).

Optimized approach

Idea

Start from brute force

The brute force calls ways(i − 1) and ways(i − 2) from scratch, so the same smaller answers are rebuilt many times. The memo fixes that, but it still keeps every answer in an array.

Find the repeated work

Under ways(5), the subtree for ways(3) is solved twice and ways(2) three times. Each repeat gives the same number as the first time.

Define the state — what variables do I need?

prev2: The number of ways to reach step i − 2.
prev1: The number of ways to reach step i − 1.
i: The step being built now, from 3 up to n.

Define validity

The count for step i is exactly the count for step i − 1 plus the count for step i − 2, because the last move is either a 1-step or a 2-step.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

prev2 = 1, prev1 = 2

These are the answers for steps 1 and 2. Every later step is built from them.

Each step i from 3 to n

cur = prev1 + prev2; then prev2 = prev1 and prev1 = cur

cur is ways(i). The old prev1 is ways(i − 1), which becomes prev2 for the next step, and cur becomes prev1.

What does the current window add to the answer?

Nothing is collected along the way. When the loop ends, prev1 holds ways(n), which is the answer.

Code & Implementation

optimal.cpp

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;                    // ways(1) = 1, ways(2) = 2
        int prev2 = 1;                           // ways(i - 2), starts at ways(1)
        int prev1 = 2;                           // ways(i - 1), starts at ways(2)
        for (int i = 3; i <= n; i++) {
            int cur = prev1 + prev2;             // ways(i) = ways(i - 1) + ways(i - 2)
            prev2 = prev1;                       // slide both values up one step
            prev1 = cur;
        }
        return prev1;
    }
};

Complexity

Time O(N)Space O(1)

Here N is n. The loop runs once for each step from 3 to n, with one addition each. Only two variables are stored. An int is enough, because the largest answer, ways(45) = 1836311903, is below 2^31 − 1.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Recursive ways(i) = ways(i−1) + ways(i−2), with no memory	O(2^N)	O(N)
Better	The same recursion, but store each ways(i) the first time it is computed	O(N)	O(N)
Optimal	Keep only the last two answers in two variables and build up from step 3	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“how many ways”The question asks for a count, not the list of moves. Build the count step by step, and do not list the paths.
“climb 1 or 2 steps”The choice at each step only looks back one or two steps, so the answer for step i depends only on steps i − 1 and i − 2.
“reach the top”The top is a fixed target, step n. Fill the answers from the bottom up to n.

Count the ways to reach step n+each move is 1 or 2 steps+answer(i) depends only on answer(i − 1) and answer(i − 2)→DP 1D — Fibonacci-style (two variables)

This is the anchor of the Fibonacci-style sub-pattern: the answer at step i depends on the two steps before it, so the table can shrink to two variables. Each move only looks back one or two steps, and the count itself is a plain sum with no cost or rule to check. Min Cost Climbing Stairs keeps the same two-step shape but adds a cost to each step, and Decode Ways adds a rule that decides when a step can be used at all.

Don't make this mistake

Pattern confusion: listing every path (backtracking)

✗ void dfs(int left, vector<int>& path, vector<vector<int>>& out) { if (left == 0) { out.push_back(path); return; } for (int s = 1; s <= 2 && s <= left; s++) { path.push_back(s); dfs(left - s, path, out); path.pop_back(); } } // ... return out.size();

✓ int prev2 = 1, prev1 = 2; for (int i = 3; i <= n; i++) { int cur = prev1 + prev2; prev2 = prev1; prev1 = cur; } return prev1;

The problem asks for a count, but this search builds every list of moves. For n = 5 it makes 20 calls and writes out 8 lists. The DP fills 5 cells, one per step. For n = 45 there are 1836311903 lists, so listing them is impossible. You only need the count, so you never need to build a list.

Wrong base case for two steps

✗ if (n <= 2) return 1;

✓ if (n <= 2) return n;

Two steps can be climbed as 1 + 1 or as one 2-step, which is 2 ways, not 1. With the wrong base, n = 2 returns 1. If the same wrong base sits in the recursion (if (i <= 2) return 1;), then n = 3 gives ways(2) + ways(1) = 1 + 1 = 2 instead of 3.

Loop starts one step too early

✗ int prev2 = 1, prev1 = 2; for (int i = 2; i <= n; i++) { int cur = prev1 + prev2; prev2 = prev1; prev1 = cur; }

✓ int prev2 = 1, prev1 = 2; for (int i = 3; i <= n; i++) { int cur = prev1 + prev2; prev2 = prev1; prev1 = cur; }

The two starting values already cover steps 1 and 2. Starting at i = 2 adds an extra step. For n = 3 the wrong loop runs twice, producing 3 and then 5, and returns 5. The answer is 3.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — 1D Linear translate into production architectures and low-level memory mechanics.

LLD Architecture