Climbing Stairs - Leetcode Solution

Problem Link

Brute Force Method

Understand the problem: Find the number of distinct ways to climb n stairs, taking 1 or 2 steps at a time.
Use recursion to compute the number of ways:
If n equals 1, return 1, as there is only one way (one step).
If n equals 2, return 2, as there are two ways (two 1-steps or one 2-step).
For n > 2, the number of ways is the sum of ways to climb n-1 stairs (taking 1 step) and n-2 stairs (taking 2 steps).
Return the recursive sum of climbStairs(n-2) and climbStairs(n-1).

Code Solution (Brute Force)

# Recursive Solution
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        
        return self.climbStairs(n-2) + self.climbStairs(n-1)
        # Time: O(2^n)
        # Space: O(n)

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        return climbStairs(n-2) + climbStairs(n-1);
    }
};

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        return climbStairs(n-2) + climbStairs(n-1);
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n === 1) return 1;
    if (n === 2) return 2;
    
    return climbStairs(n-2) + climbStairs(n-1);
};

Why the Brute-Force Solution is Inefficient

The brute-force solution uses naive recursion, leading to:

Time Complexity: O(2^n), as each call branches into two recursive calls, forming a binary tree of depth n.
Space Complexity: O(n), due to the recursion stack.
Performance Issue: The exponential time complexity causes significant slowdowns for large n, as many subproblems are recomputed repeatedly.

Top Down Method

Initialize Memoization Dictionary: We create a dictionary memo to store the number of ways to climb i steps for specific values of i. It is initialized with base cases: memo[1] = 1 (there is 1 way to climb 1 step: take one 1-step) and memo[2] = 2 (there are 2 ways to climb 2 steps: two 1-steps or one 2-step).
Define Recursive Function: We define a helper function f(n) that computes the number of ways to climb n steps:
- Base Case Check: If n is in memo, return the stored value memo[n]. This avoids recomputing results for previously solved subproblems.
- Recursive Case: If n is not in memo, compute the number of ways to climb n steps by summing the ways to climb n-2 steps (followed by a 2-step) and n-1 steps (followed by a 1-step). Store the result in memo[n] as f(n-2) + f(n-1) and return it.
Execute and Return: Call f(n) with the input n and return the result, which represents the total number of distinct ways to climb n steps.

Code Solution (Top Down)

# Top Down Memoization
class Solution:
    def climbStairs(self, n: int) -> int:
        memo = {1:1, 2:2}
        def f(n):
            if n in memo:
                return memo[n]
            else:
                memo[n] = f(n-2) + f(n-1)
                return memo[n]
        
        return f(n)
        # Time: O(n)
        # Space: O(n)

#include <unordered_map>
class Solution {
public:
    int climbStairs(int n) {
        unordered_map<int, int> memo = {{1, 1}, {2, 2}};
        
        function<int(int)> f = [&](int n) -> int {
            if (memo.find(n) != memo.end()) {
                return memo[n];
            }
            memo[n] = f(n-2) + f(n-1);
            return memo[n];
        };
        
        return f(n);
    }
};

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int climbStairs(int n) {
        Map<Integer, Integer> memo = new HashMap<>();
        memo.put(1, 1);
        memo.put(2, 2);
        
        class Helper {
            int f(int n) {
                if (memo.containsKey(n)) {
                    return memo.get(n);
                }
                memo.put(n, f(n-2) + f(n-1));
                return memo.get(n);
            }
        }
        
        Helper helper = new Helper();
        return helper.f(n);
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const memo = {1: 1, 2: 2};
    
    const f = (n) => {
        if (n in memo) {
            return memo[n];
        }
        memo[n] = f(n-2) + f(n-1);
        return memo[n];
    };
    
    return f(n);
};

Bottom Up Method

Handle Base Cases: If n == 1, there is only 1 way to climb 1 step (take one 1-step), so return 1. If n == 2, there are 2 ways to climb 2 steps (two 1-steps or one 2-step), so return 2. These checks handle the smallest inputs directly.
Initialize DP Array: We create an array dp of size n to store the number of ways to climb i+1 steps at index i. Initialize dp[0] = 1 (ways to climb 1 step) and dp[1] = 2 (ways to climb 2 steps) as the base cases for the dynamic programming approach.
Fill DP Array: For each step i from 2 to n-1 (corresponding to 3 to n steps):
- Compute dp[i] as the sum of dp[i-2] (ways to climb i-1 steps, followed by a 2-step) and dp[i-1] (ways to climb i steps, followed by a 1-step).
- This reflects the fact that to reach step i+1, you can come from step i-1 (via a 2-step) or step i (via a 1-step).
Return Result: Return dp[n-1], which represents the number of ways to climb n steps.

Code Solution (Bottom Up)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        
        dp = [0] * n
        dp[0] = 1
        dp[1] = 2

        for i in range(2, n):
            dp[i] = dp[i-2] + dp[i-1]
        
        return dp[n-1]
        # Time: O(n)
        # Space: O(n)

#include <vector>
class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        std::vector<int> dp(n);
        dp[0] = 1;
        dp[1] = 2;
        
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i-2] + dp[i-1];
        }
        
        return dp[n-1];
    }
};

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        int[] dp = new int[n];
        dp[0] = 1;
        dp[1] = 2;
        
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i-2] + dp[i-1];
        }
        
        return dp[n-1];
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n === 1) return 1;
    if (n === 2) return 2;
    
    let dp = new Array(n).fill(0);
    dp[0] = 1;
    dp[1] = 2;
    
    for (let i = 2; i < n; i++) {
        dp[i] = dp[i-2] + dp[i-1];
    }
    
    return dp[n-1];
};

💡Optimal Solution: Constant Space

Remove DP Array: Instead of using a dp array of size n, the solution introduces two variables:
- two_back: Initialized to 1, representing the number of ways to climb 1 step (equivalent to dp[0]).
- one_back: Initialized to 2, representing the number of ways to climb 2 steps (equivalent to dp[1]).
These variables store the results for the previous two steps, which are sufficient to compute the next step’s value.
Iterative Computation with Variables: The loop from i = 2 to n-1 is retained, but instead of filling a dp array, it computes the number of ways for the current step using the variables:
- Compute next_num = two_back + one_back, which represents the number of ways to climb i+1 steps (equivalent to dp[i] in the first solution).
- Update the variables for the next iteration: set two_back = one_back (shift the previous step’s value) and one_back = next_num (store the current step’s value).
This mimics the recurrence relation dp[i] = dp[i-2] + dp[i-1] but only keeps the two values needed at each step.
Return Result: After the loop, one_back holds the number of ways to climb n steps (equivalent to dp[n-1]), so we return one_back.

Code Solution (Constant Space)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        
        two_back = 1
        one_back = 2
        for i in range(2, n):
            next_num = two_back + one_back
            two_back = one_back
            one_back = next_num
        
        return one_back
        # Time: O(n)
        # Space: O(1)

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;

        int twoBack = 1;
        int oneBack = 2;

        for (int i = 2; i < n; ++i) {
            int nextNum = twoBack + oneBack;
            twoBack = oneBack;
            oneBack = nextNum;
        }

        return oneBack;
    }
};

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;

        int twoBack = 1;
        int oneBack = 2;

        for (int i = 2; i < n; i++) {
            int nextNum = twoBack + oneBack;
            twoBack = oneBack;
            oneBack = nextNum;
        }

        return oneBack;
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n === 1) return 1;
    if (n === 2) return 2;

    let twoBack = 1;
    let oneBack = 2;

    for (let i = 2; i < n; i++) {
        const nextNum = twoBack + oneBack;
        twoBack = oneBack;
        oneBack = nextNum;
    }

    return oneBack;
};

Detailed Explanation

Understanding the Fibonacci Number Problem

The Fibonacci Number problem asks you to compute the n^th number in the famous Fibonacci sequence, where each number is the sum of the two preceding ones. The sequence starts with 0 and 1, and is defined as:

F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2) for n ≥ 2.

This is a fundamental dynamic programming problem and appears frequently in interviews and algorithm practice.

Brute-Force Approach and Its Drawbacks

A naive solution uses direct recursion: for each call to fib(n), you recursively calculate fib(n - 1) and fib(n - 2). While conceptually simple, this approach is highly inefficient.

The recursive tree grows exponentially in size, and the same values are recalculated many times. For example, to compute fib(5), fib(3) and fib(2) are each called multiple times.

This leads to a time complexity of O(2ⁿ), making it infeasible for larger input values like n = 40 or higher.

Optimized Dynamic Programming Strategy

To avoid recomputation, we can use a bottom-up iterative approach that builds the solution from the ground up. This technique eliminates recursion and uses just two variables to hold the previous Fibonacci values.

We initialize prev = 0 and cur = 1. Then for each step from 2 to n, we update cur to be prev + cur and shift prev to the old value of cur.

This results in a time complexity of O(n) and a space complexity of O(1), making it extremely efficient and scalable.

Key Takeaways for Interviews

Always look for overlapping subproblems in recursive solutions — a sign that dynamic programming might help.
Understand both the recursive and iterative approaches so you can explain trade-offs between readability and performance.
Practice optimizing brute-force problems by converting them to bottom-up dynamic programming techniques.

Get Personalized Support at AlgoMap Bootcamp 💡