LeetCode #70: Climbing Stairs

05 Aug, 2025

Mastering LeetCode #70: Climbing Stairs - From Brute Force to Space-Optimized Dynamic Programming

The Climbing Stairs problem is a classic dynamic programming question that elegantly demonstrates the evolution from naive recursive solutions to highly optimized algorithms. This problem serves as an excellent introduction to dynamic programming concepts and showcases how we can progressively optimize our solutions.

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 = 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

Understanding the Problem

Let's visualize this problem with a simple diagram:

The key insight is recognizing the recursive pattern. This essentially turns out to be a series of Fibonacci numbers, where the number of ways to climb stairs n, if we can only climb 1 or 2 stairs every time gives us the following observation:

1. To climb 1 stair, you have only 1 way: 1
2. To climb 2 stairs you have 2 ways: [1 then 1, 2]
3. To climb 3 stairs you have ways to climb (3-1) + (3-2) stairs = [1 then 1 then 1, 1 then 2, 2 then 1]

This gives us the recurrence relation: climb(n) = climb(n-1) + climb(n-2)

Approach 1: Brute Force Recursion

The most intuitive approach directly implements the recurrence relation.

int climbStair(int n){
    if (n <= 2) return n;
    return climbStair(n-1) + climbStair(n-2);
}

Time Complexity: O(2^n) - Exponential Space Complexity: O(n) - Due to recursion stack

Problem: This approach will only work for small cases, and will give us TLE (Time Limit Exceeded) on larger cases. The issue is that we recalculate the same subproblems multiple times, leading to exponential time complexity.

Approach 2: Top-Down Dynamic Programming (Memoization)

This is essentially a "smarter" recursion. We start from the top (the goal n) and break it down into smaller subproblems. To avoid re-calculating the same subproblem over and over we store (or "memorize") the results in a cache (like an array or a hash map).

Analogy: We start with asking for climbStairs for n. Then we return the climbStairs for N = climbStairs for (n - 1) + climbStairs for (n - 2).

Top-Down Flow

The "top-down" designation arises because this approach starts with the main problem and recursively breaks it down into subproblems, solving them as needed, and storing their results along the way. The computation flows from the "top" (the original problem) down to its base cases.

How Memoization Works

1. Recurse Down: Start with the goal climb(n). The function calls itself for climb(n-1) and climb(n-2).

2. Check Cache: Before computing anything, check if the result for the current step is already in your cache. If yes, return it immediately. Here we use memo as the array that stores the previous results.

3. Compute & Store: If the result isn't in the cache, compute it by making the recursive calls. Then, store this new result in the cache before returning it.

4. Recursive Structure: The problem is initially solved using a straightforward recursive function that breaks it down into smaller subproblems.

Memoization Concept (Caching)

To address the exponential time complexity, a data structure (like an array, hash map, or dictionary) is used as a "memo" or cache. Before computing a subproblem's solution, the algorithm first checks if the result for that specific input is already stored in the memo:

• If found: The cached result is immediately returned, avoiding redundant computations.
• If not found: The subproblem is computed recursively. Once the result is obtained, it is stored in the memo for future use before being returned.

Advantages of Memoization

1. Clarity and Simplicity: Often easier to conceptualize and implement than the iterative "bottom-up" approach, as it closely mirrors the natural recursive definition of the problem.

2. Calculates only necessary subproblems: Unlike tabulation (bottom-up), which might compute all possible subproblems, memoization only calculates those subproblems that are actually required to solve the main problem.

Disadvantages of Memoization

1. Recursion Overhead: Relies on recursion, which can incur overhead due to function call stack management.
2. Stack Overflow Risk: Deep recursion can lead to stack overflow errors for very large problem instances.

class Solution{
public:
    int climbStairs(int n){
        vector<int> memo(n+1);
        return climb(n, memo);
    }

    int climb(int n, vector<int> &memo){
        if (n < 0) return 0;
        if (n == 0) return 1;

        if(memo[n] > 0) return memo[n];

        memo[n] = climb(n-1, memo) + climb(n-2, memo);

        return memo[n];
    }
};

Time Complexity: O(n) - Each subproblem is solved only once Space Complexity: O(n) - Memoization array + recursion stack

Approach 3: Bottom-Up Dynamic Programming (Tabulation)

Dynamic Programming's bottom-up approach, known as tabulation, solves problems by iteratively building solutions from the base cases to the final desired solution. This method contrasts with the top-down approach (memoization), which uses recursion with caching.

Key Characteristics of Tabulation

1. Iterative Construction: Instead of recursive calls, tabulation uses loops to compute solutions for subproblems in a systematic order.

2. Table Storage: Solutions to subproblems are stored in a data structure, typically an array or a table, to avoid redundant computations.

3. Base Case Initialization: The table is initialized with the solutions to the smallest, fundamental subproblems (base cases).

4. Building Upwards: Subsequent entries in the table are calculated using the already computed values of smaller subproblems, moving towards the solution of the main problem.

Example: Fibonacci Sequence using Tabulation

To calculate the Nth Fibonacci Number F(N) using tabulation:

1. Create a table: Initialize an array dp of size N+1.
2. Base cases: Set dp[0] = 0 and dp[1] = 1.
3. Iterative calculation: Loop from i = 2 to N, calculating dp[i] = dp[i-1] + dp[i-2].
4. Result: The value dp[N] holds the Nth Fibonacci number.

Advantages of Tabulation

1. Iterative approach: Avoids recursion overhead and the risk of stack overflow.

2. Space efficiency: Can often be optimized to use less memory by only storing the necessary previous values (e.g., only the last two Fibonacci numbers are needed to calculate the next).

3. Cache-friendliness: Iterative access patterns can lead to better cache performance.

4. Easier analysis: Time and space complexity are often easier to analyze due to the explicit loop structure.

5. Debuggability: The intermediate results stored in the table can be easily examined for debugging.

When to Use Tabulation

Tabulation is particularly well-suited for problems where:

• All subproblems need to be solved to arrive at the final solution.
• The problem has a predictable, iterative structure.
• Space optimization is crucial or there's a need to avoid recursion-related issues like stack overflows.

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

        vector<int> dp(n+1);

        dp[1] = 1; // 1 way to reach step 1
        dp[2] = 2; // 2 ways to reach step 2

        // Fill the table bottom-up
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }

        return dp[n];
    }
};

Time Complexity: O(n) - Single loop through all steps Space Complexity: O(n) - DP array storage

Approach 4: Space-Optimized Dynamic Programming

The core idea here is that to calculate the number of ways to get to any step i, we need to know the results of only the two preceding steps i-1 and i-2. We don't need the entire history of steps from 1 to i-3.

How the Space-Optimized Code Works

Think of the variables prev2 and prev1 as a "sliding window" of the last two results, moving up the staircase one step at a time.

1. Base Cases: The code first handles the simplest cases. If n is 1 or 2, the number of ways is simply n.

2. Initialization: For any step i greater than 2, we need the result for the two previous steps. The loop starts at i = 3, so we initialize our variables to represent the results for steps 1 and 2.

3. The Loop (The Slide): The for loop iterates from step 3 up to the target step n. Let's trace it for n = 5:

   Initial State: prev2 = 1 and prev1 = 2

   i = 3:

   • current = prev1 + prev2 → current = 2 + 1 = 3. Correct, ways(3) = 3
   • prev2 = prev1; → prev2 is now 2.
   • prev1 = current; → prev1 is now 3.
   • Our window has slid, it now holds ways(2) and ways(3).

   i = 4:

   • current = prev1 + prev2 → current = 3 + 2 = 5. Correct, ways(4) = 5.
   • prev2 = prev1; → prev2 is now 3.
   • prev1 = current → prev1 is now 5.
   • Our window now holds ways(3) and ways(4).

   i = 5:

   • current = prev1 + prev2 → current = 5 + 3 = 8. (Correct, ways(5) = 8)
   • prev2 = prev1; → prev2 is now 5.
   • prev1 = current; → prev1 is now 8.
   • The window now holds ways(4) and ways(5).

The loop finishes when i = n. The last calculated current value is the number of ways to reach the n-th step, which is then returned.

Why Space Optimization is Better than Standard Bottom-Up

The advantage is purely about space efficiency:

• Standard Bottom-Up (Tabulation): This approach uses an array (e.g. int dp[n+1]) to store the result for every single step from 1 to n.

  • Space Complexity: O(N)

• Space Optimized Bottom Up: This approach only uses a few variables prev1, prev2, and current to store the necessary information. The amount of memory used does not change, no matter how large n gets.

  • Space Complexity: O(1) i.e. constant space.
  • If n is 1,000,000 you still only need three integers.

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        
        int prev2 = 1; // ways(1)
        int prev1 = 2; // ways(2)
        int current;
        
        for (int i = 3; i <= n; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        
        return current;
    }
};

Time Complexity: O(n) - Single loop Space Complexity: O(1) - Only three variables

Comprehensive Comparison: Memoization vs Tabulation

Tabulation and memoization (the top-down approach) are both dynamic programming techniques, but they differ in their implementation strategies. Memoization uses recursion and stores results in a cache, while tabulation employs an iterative approach and fills a table in a bottom-up manner. The choice between them depends on the specific problem and desired trade-offs between elegance of code, memory efficiency, and recursion depth limitations.

Performance Comparison

Key Takeaways

1. Pattern Recognition: Identifying the Fibonacci-like recurrence relation is crucial
2. Optimization Journey: From exponential to linear time, then from linear to constant space
3. Trade-offs: Memoization vs. Tabulation - recursion elegance vs. iterative efficiency
4. Space Optimization: Often possible when only a fixed number of previous states are needed

Common Variations

This pattern applies to many similar problems:

• Coin Change: Minimum coins needed
• House Robber: Maximum money without robbing adjacent houses
• Decode Ways: Number of ways to decode a string

Interview Tips

1. Start with the recurrence relation - establish the mathematical foundation
2. Implement brute force first - shows understanding of the problem
3. Optimize step by step - demonstrate problem-solving progression
4. Analyze complexity - time and space for each approach
5. Consider edge cases - n=0, n=1, n=2

The Climbing Stairs problem beautifully illustrates the power of dynamic programming and the importance of recognizing optimization opportunities. Mastering this progression from brute force to space-optimized solutions will serve you well in tackling more complex dynamic programming challenges.