Interview Problem Explained: Climbing Stairs (LeetCode 70, Recursion & DP)

Climbing Stairs: Problem Statement

Your are faced with a challenge: climb to the top of a staircase with N steps. Each time, you can climb either 1 or 2 steps. Given N, calculate the total number of distinct ways to reach the top.

Examples:

• N = 2: [1+1], 2 → 2 ways

• N = 3: [1+1+1], [1+2], [2+1] → 3 ways

• N = 4: [1+1+1+1], [1+1+2], [1+2+1], [2+1+1], [2+2] → 5 ways

Constraints:

• 1 ≤ N ≤ 45

Tip: This is LeetCode Problem #70.
LeetCode’s problem statements are often concise, which can leave some concepts unclear.
Here at Codetree, we break things down with examples and step-by-step guidance for deeper understanding.

Step 1: Naive Recursive Approach (O(2ⁿ))

Idea

Why use recursion? Recursion is the most intuitive way to break a problem into smaller subproblems. The simplest method is to count all possible ways directly using recursion.

Reduce the "remaining steps" with each recursive call. The function takes the number of remaining steps n as its parameter.

Logic Breakdown

Base cases for the recursive function:

• n = 0: Reached the top → count 1 way

• n = 1: One step left → only one way to finish

Code Implementation

answer = 0
def climb_stairs(n):
    global answer
    if n == 0 or n == 1:
        answer += 1
        return
    climb_stairs(n-1)  # Take 1 step
    climb_stairs(n-2)  # Take 2 steps

Time & Space Complexity

The recursion tree for N=5 looks like this:

Each level makes 2 recursive calls. So the time complexity is O(2ⁿ).

For N = 45, this results in ~35 trillion calls — guaranteed timeout.

Step 2: Recursive Return Value

Idea

In Step 1, we used a global variable to count the number of ways. Now, let’s compute the result using return values instead. This helps set up for a future DP transformation.

Logic Breakdown

def climb_stairs(n):
    if n == 0 or n == 1:
        return 1
    return climb_stairs(n-1) + climb_stairs(n-2)

• Return 1 for n == 0 or n == 1

• Otherwise, return the sum of ways from n-1 and n-2

This structure eliminates the need for a global variable, making the code cleaner and easier to upgrade to DP.

Step 3. Memoization (Top-Down DP)

Idea

In the recursion tree, calls like climb_stairs(3) and climb_stairs(2) are repeated many times.

This redundant computation explodes as N increases, leading to O(2ⁿ) time complexity.

Dynamic Programming (DP) eliminates redundant work by storing results of subproblems and reusing them.

What is Memoization?

Memoization means caching the results of expensive function calls and returning the cached result when the same inputs occur again. This avoids repeated calculations and greatly improves efficiency.

Let’s apply memoization to the Climbing Stairs problem.

Logic Breakdown

• Eliminate redundant computations

  • Store the result of climb_stairs(k) once it's calculated, and reuse it when the same input appears again.

• Memoization

  • Prepare a memo (e.g., a memo dictionary) to store previously computed results.

  • If the result for n is not in the memo, calculate it recursively and store it.

  • If it is already stored, return memo[n] directly without further recursion.

→ By avoiding redundant computations, we can reduce the time complexity from O(2ⁿ) to O(N).

Code Implementation

memo = {}
def climb_stairs(n):
    if n == 0 or n == 1:
        return 1
    if n not in memo:
        memo[n] = climb_stairs(n-1) + climb_stairs(n-2)
    return memo[n]

Time & Space Complexity

• Time Complexity: O(N) Each state is computed only once.

• Space Complexity: O(N) For the recursion stack and memoization storage.

Step 4. Tabulation (Bottom-Up DP)

Idea

Memoization solves the problem from the top down-starting with the big problem and recursively solving smaller ones.

Tabulation is the opposite: it solves from the bottom up, building solutions to small subproblems first and combining them to solve the original problem.

For Climbing Stairs, you precompute the number of ways to reach steps 1 and 2, then use those to compute steps 3, 4, ..., N in order.

Tabulation is fast, stable, and easy to implement with loops.

Key Elements of Tabulation

When solving a dynamic programming (DP) problem using tabulation, there are three essential components you need to define:

1. State Definition (DP Definition):

   • This plays the same role as the memo in the memoization approach.

   • You must decide what value to store and how to use it.

   • In this problem, we define it as: → dp[i] = the number of distinct ways to reach the i-th stair.

2. Recurrence Relation:

   • This expresses the relationship between the current state and its previous states using a formula.

   • For this problem, the recurrence is: → dp[i] = dp[i-1] + dp[i-2]

     • Because the number of ways to reach the i-th stair equals: (ways to reach the (i-1)-th stair and take one step) + (ways to reach the (i-2)-th stair and take two steps).

3. Base Cases:

   • These are the smallest subproblems that cannot be broken down further and must be manually defined.

   • For this problem: → dp[0] = 1 (One way to stay at the base without climbing) → dp[1] = 1 (One way to climb directly to the first stair)

See also: Fibonacci Number DP

Code Implementation

def climb_stairs(n):
    # Exception handling
    if n <= 1:
        return 1
    
    # Initialize the dp array
    dp = [0] * (n + 1)
    dp[0] = 1  # Set base case
    dp[1] = 1  # Set base case
    
    # Fill values using Bottom-up approach
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]  # Apply recurrence relation
    
    return dp[n]  # Return the result

Time & Space Complexity

• Time Complexity: O(N)

  • Each value from 2 to N is computed exactly once, resulting in a total of N - 1 operations.

• Space Complexity: O(N)

  • A dp array of length N + 1 is used, so the space requirement is proportional to N.

Tabulation is simple, intuitive, and avoids redundant calculations-making it ideal for this problem.

Frequently Asked Questions

Q. Why is the recursive approach inefficient?

A: While recursion is intuitive, it incurs heavy time and memory overhead due to repeated subproblem calls. This is especially problematic when the same subproblem is solved many times.

Q. Memoization vs. Tabulation: Which is better?

A: Tabulation is generally faster and more predictable, as it uses loops instead of recursion. However, for complex state spaces, memoization can be easier to implement. Choose the method that best fits the problem.

Q. What type of algorithm is this problem?

A: This is a classic dynamic programming problem with a recurrence similar to the Fibonacci sequence. It’s perfect for practicing state definition, recurrence, and base cases.

How to Prepare for Interviews with the Climbing Stairs Problem

The ‘Climbing Stairs’ problem is a textbook example of how to evolve your thinking from recursion to memoization to tabulation.

By working through each approach, you’ll internalize key DP concepts: eliminating redundant work, defining states, and building recurrence relations.

Practice these skills:

• Understand the structural inefficiency of naive recursion

• Learn how memoization and tabulation improve performance

• Strengthen your intuition for recurrence relations and base cases

Similar problems to practice

• 509. Fibonacci Number

• 746. Min Cost Climbing Stairs

• 198. House Robber

• Filling a Rectangle 2

How to Review After Solving This Problem

1. Comparing time complexities Try different N values and see the performance gap.

2. Solving the problem in all three ways Focus on the core idea, not just the code.