Skip to main content
CodePeetCodePeet
CodePeet 250

Climbing Stairs

EASYProblemSolveExternal Links

Description

You are climbing a staircase that has n steps to reach the top. Starting from the ground (step 0), each time you can climb either 1 step or 2 steps upward.

Return the number of distinct ways you can climb to the top (step n).

Examples

Example 1

Input: n = 2

Output: 2

Explanation: There are two distinct ways to climb to the top:

  1. 1 step + 1 step
  2. 2 steps

Example 2

Input: n = 3

Output: 3

Explanation: There are three distinct ways to climb to the top:

  1. 1 step + 1 step + 1 step
  2. 1 step + 2 steps
  3. 2 steps + 1 step

Example 3

Input: n = 4

Output: 5

Explanation: There are five distinct ways to reach step 4:

  1. 1 + 1 + 1 + 1
  2. 1 + 1 + 2
  3. 1 + 2 + 1
  4. 2 + 1 + 1
  5. 2 + 2

Constraints

  • 1 ≤ n ≤ 45

Editorial

Brute Force

Intuition

The most natural approach is to think about the problem from the destination and work backwards. To reach step n, you must have arrived from either step n - 1 (by taking 1 step) or step n - 2 (by taking 2 steps). So the number of ways to reach step n is the sum of the ways to reach step n - 1 and step n - 2.

This is exactly the same pattern as the Fibonacci sequence! The ways to climb n stairs follows: ways(0) = 1, ways(1) = 1, ways(2) = 2, ways(3) = 3, ways(4) = 5, and so on.

Imagine you are standing on a staircase and want to count all possible routes to the top. At every step, you face a fork: take one step or two. Each choice leads to a different sub-staircase, and you recursively count the routes from there. This exhaustive exploration gives the correct count but does enormous redundant work.

Step-by-Step Explanation

Let's trace through with n = 4:

Step 1: Call countWays(4). To reach step 4, we come from step 3 (take 1) or step 2 (take 2). So countWays(4) = countWays(3) + countWays(2).

Step 2: Compute countWays(3). countWays(3) = countWays(2) + countWays(1).

Step 3: Compute countWays(2) (first occurrence). countWays(2) = countWays(1) + countWays(0).

Step 4: countWays(1) = 1 (base case: one way to climb 1 stair). countWays(0) = 1 (base case: one way to stay at ground). So countWays(2) = 1 + 1 = 2.

Step 5: Back in countWays(3): we need countWays(1) = 1 (base case). So countWays(3) = 2 + 1 = 3.

Step 6: Now compute countWays(2) for the right branch of countWays(4). This is the SAME subproblem we already solved in Step 3-4! But without memoization, we compute it again: countWays(2) = countWays(1) + countWays(0) = 1 + 1 = 2.

Step 7: countWays(4) = countWays(3) + countWays(2) = 3 + 2 = 5.

Result: There are 5 distinct ways to climb 4 stairs.

Recursive Exploration of Climbing Stairs (n=4) — Watch how the recursion tree branches at each step, calling countWays(n-1) and countWays(n-2). Notice how countWays(2) is computed multiple times — this redundancy is what makes brute force exponential.

Algorithm

  1. Define a recursive function countWays(n) that returns the number of ways to climb n stairs
  2. Base cases: If n == 0 or n == 1, return 1 (one way to stay put, one way to take a single step)
  3. Recursive case: Return countWays(n - 1) + countWays(n - 2) — the ways from taking 1 step plus the ways from taking 2 steps
  4. Call countWays(n) to get the answer

Code

class Solution {
public:
    int climbStairs(int n) {
        if (n == 0 || n == 1)
            return 1;
        
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
};
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 0 or n == 1:
            return 1
        
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)
class Solution {
    public int climbStairs(int n) {
        if (n == 0 || n == 1)
            return 1;
        
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

Complexity Analysis

Time Complexity: O(2ⁿ)

Each call branches into two recursive calls. The recursion tree has depth n, and in the worst case the tree is nearly full, leading to approximately 2ⁿ nodes. For n = 45 (the maximum constraint), this means around 2⁴⁵ ≈ 35 trillion operations — completely infeasible.

Space Complexity: O(n)

The recursion stack can go at most n levels deep (one level per stair descended). Each stack frame uses constant space, so the total stack space is O(n).

Why This Approach Is Not Efficient

The recursive solution has exponential time complexity O(2ⁿ) because it recomputes the same subproblems many times. In our trace of n = 4, countWays(2) was computed twice, countWays(1) was computed three times, and countWays(0) was computed twice. For larger values of n, this redundancy grows explosively.

The key insight is that there are only n + 1 unique subproblems (countWays(0) through countWays(n)), but the recursion tree has O(2ⁿ) nodes. The vast majority of nodes are duplicates. For n = 45, the brute force makes trillions of calls while only 46 unique answers exist.

We can fix this by storing the result of each subproblem the first time it is computed. Using a DP table, we reduce time from O(2ⁿ) to O(n) while keeping space at O(n).

Better Approach - Dynamic Programming (Tabulation)

Intuition

Instead of starting at the top and recursing down (which causes redundant recomputation), we can build the answer from the bottom up. We know:

  • dp[0] = 1 (one way to stay at ground)
  • dp[1] = 1 (one way to reach step 1)

For every step i from 2 to n, the number of ways to reach step i is:
dp[i] = dp[i - 1] + dp[i - 2]

because you can arrive at step i by taking a 1-step from step i-1 OR a 2-step from step i-2.

This is exactly computing the Fibonacci sequence! We fill a table from left to right, where each new value depends only on the two values before it. No recursion, no redundancy — each value is computed exactly once.

Step-by-Step Explanation

Let's trace through with n = 5:

Step 1: Create a DP array of size n + 1 = 6. Set dp[0] = 1 and dp[1] = 1.

Step 2: Compute dp[2] = dp[1] + dp[0] = 1 + 1 = 2. There are 2 ways to climb 2 stairs.

Step 3: Compute dp[3] = dp[2] + dp[1] = 2 + 1 = 3. There are 3 ways to climb 3 stairs.

Step 4: Compute dp[4] = dp[3] + dp[2] = 3 + 2 = 5. There are 5 ways to climb 4 stairs.

Step 5: Compute dp[5] = dp[4] + dp[3] = 5 + 3 = 8. There are 8 ways to climb 5 stairs.

Result: dp[5] = 8.

Bottom-Up DP Table for Climbing Stairs (n=5) — Watch the 1D DP table fill from left to right. Each cell stores the number of ways to reach that stair, computed as the sum of the two preceding cells — just like the Fibonacci sequence.

Algorithm

  1. Create a DP array of size n + 1
  2. Set base cases: dp[0] = 1, dp[1] = 1
  3. For i from 2 to n:
    • dp[i] = dp[i - 1] + dp[i - 2]
  4. Return dp[n]

Code

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return 1;
        
        vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
};
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return 1
        
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1
        
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        
        return dp[n]
class Solution {
    public int climbStairs(int n) {
        if (n <= 1) return 1;
        
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate from 2 to n, performing one addition per step. Each of the n - 1 iterations takes O(1) time, giving O(n) total.

Space Complexity: O(n)

We store a DP array of size n + 1. For the maximum constraint n = 45, this is just 46 integers — extremely manageable. However, we can do even better on space since each cell only depends on the two cells before it.

Why This Approach Is Not Efficient

The DP tabulation approach runs in O(n) time, which is optimal for this problem (we must at minimum read the problem size n). However, it uses O(n) extra space for the DP array.

Looking at the recurrence dp[i] = dp[i-1] + dp[i-2], each new value depends on only the two most recent values. Once we compute dp[i], we never need dp[i-3], dp[i-4], etc. again. Storing the entire array wastes space on values we will never revisit.

We can reduce space from O(n) to O(1) by keeping just two variables — the previous two values — and updating them as we go. This gives us the same O(n) time with O(1) space.

Optimal Approach - Space-Optimized DP

Intuition

Since each Fibonacci-like value depends only on the two values before it, we do not need an entire array. We just need two variables: one holding dp[i-1] and another holding dp[i-2].

Think of it like a caterpillar crawling forward: it only needs its two back legs (the two previous values) to know where to place its front leg (the next value). As it moves forward, the old back leg becomes irrelevant and gets updated.

We maintain two variables, prev2 (representing dp[i-2]) and prev1 (representing dp[i-1]). At each step, we compute curr = prev1 + prev2, then slide the window forward: prev2 takes the old prev1 value, and prev1 takes the new curr value. After n - 1 such shifts, prev1 holds the answer.

Step-by-Step Explanation

Let's trace through with n = 5:

Step 1: Initialize prev2 = 1 (representing dp[0]) and prev1 = 1 (representing dp[1]).

Step 2: i = 2: curr = prev1 + prev2 = 1 + 1 = 2. Slide: prev2 = 1 (old prev1), prev1 = 2 (curr). Now prev1 holds dp[2] = 2.

Step 3: i = 3: curr = prev1 + prev2 = 2 + 1 = 3. Slide: prev2 = 2, prev1 = 3. Now prev1 holds dp[3] = 3.

Step 4: i = 4: curr = prev1 + prev2 = 3 + 2 = 5. Slide: prev2 = 3, prev1 = 5. Now prev1 holds dp[4] = 5.

Step 5: i = 5: curr = prev1 + prev2 = 5 + 3 = 8. Slide: prev2 = 5, prev1 = 8. Now prev1 holds dp[5] = 8.

Result: prev1 = 8. There are 8 distinct ways to climb 5 stairs.

Space-Optimized DP — Rolling Two Variables (n=5) — Watch how we track only two values at a time (prev2 and prev1) and slide them forward at each step, computing the Fibonacci-like sequence without needing an entire array.

Algorithm

  1. If n <= 1, return 1 (base cases)
  2. Initialize prev2 = 1 (representing dp[0]) and prev1 = 1 (representing dp[1])
  3. For i from 2 to n:
    • Compute curr = prev1 + prev2
    • Update: prev2 = prev1, prev1 = curr
  4. Return prev1 (which now holds dp[n])

Code

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return 1;
        
        int prev2 = 1;  // dp[0]
        int prev1 = 1;  // dp[1]
        
        for (int i = 2; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1;
    }
};
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return 1
        
        prev2 = 1  # dp[0]
        prev1 = 1  # dp[1]
        
        for i in range(2, n + 1):
            curr = prev1 + prev2
            prev2 = prev1
            prev1 = curr
        
        return prev1
class Solution {
    public int climbStairs(int n) {
        if (n <= 1) return 1;
        
        int prev2 = 1;  // dp[0]
        int prev1 = 1;  // dp[1]
        
        for (int i = 2; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate from 2 to n, performing one addition and two assignments per iteration — all O(1) operations. Total: O(n). This is the same as the tabulation approach.

Space Complexity: O(1)

We use only three variables (prev2, prev1, curr) regardless of the input size. No array, no recursion stack. This is a significant improvement from O(n) space in the tabulation approach while maintaining the same O(n) time complexity.