Hey guys! Today, we're diving deep into a classic problem that's a favorite among coding interviewers: the Stair Climbing Problem on LeetCode. This problem isn't just about climbing stairs; it's about understanding dynamic programming, a powerful technique for solving optimization problems. So, buckle up, and let's get started!

Understanding the Stair Climbing Problem

So, what exactly is the Stair Climbing Problem? Imagine you're standing at the bottom of a staircase, and you want to reach the top. The catch is, you can only take one or two steps at a time. The question is: how many different ways can you climb to the top? Sounds simple, right? Well, it is, but it's also a perfect introduction to dynamic programming.

Let's break it down with an example. Suppose you have a staircase with n steps. If n is 1, there's only one way to climb: take one step. If n is 2, you can either take two single steps or one double step, giving you two ways. But what happens as n gets larger? This is where the magic of dynamic programming comes in.

Why is this a Dynamic Programming Problem? The Stair Climbing Problem exhibits two key properties that make it suitable for dynamic programming:

• Optimal Substructure: The optimal solution to the problem can be constructed from optimal solutions to its subproblems. In other words, the number of ways to reach the nth step depends on the number of ways to reach the (n-1)th and (n-2)th steps.
• Overlapping Subproblems: The subproblems are solved repeatedly. For example, to find the number of ways to reach the 5th step, you need the number of ways to reach the 4th and 3rd steps. To find the number of ways to reach the 4th step, you need the number of ways to reach the 3rd and 2nd steps. Notice how the problem of finding the number of ways to reach the 3rd step is solved multiple times.

Because of these two properties, we can use dynamic programming to solve the Stair Climbing Problem efficiently.

Different Approaches to Solve the Problem

There are several ways to tackle the Stair Climbing Problem, but we'll focus on two main approaches:

• Recursion
• Dynamic Programming (Top-Down and Bottom-Up)

1. Recursive Approach

The most intuitive approach is to use recursion. The idea is simple: the number of ways to reach the nth step is the sum of the number of ways to reach the (n-1)th step and the number of ways to reach the (n-2)th step. Here's how you can implement it in Python:

def climbStairsRecursive(n):
    if n <= 2:
        return n
    return climbStairsRecursive(n - 1) + climbStairsRecursive(n - 2)

This code is clean and easy to understand. However, it's also incredibly inefficient. The time complexity is O(2^n), which means the execution time doubles with each additional step. This is because the function recalculates the same values multiple times.

For example, if you call climbStairsRecursive(5), it will call climbStairsRecursive(4) and climbStairsRecursive(3). But climbStairsRecursive(4) will also call climbStairsRecursive(3) and climbStairsRecursive(2). See the overlap? This is why recursion, while simple, is not the best approach for this problem.

2. Dynamic Programming

Dynamic programming optimizes recursive solutions by storing the results of subproblems to avoid redundant calculations. There are two main ways to implement dynamic programming:

• Top-Down (Memoization): Start with the main problem and break it down into subproblems, storing the results in a memo (usually a dictionary or array) as you go.
• Bottom-Up (Tabulation): Start with the smallest subproblems and build up to the main problem, storing the results in a table (usually an array).

Top-Down (Memoization)

Memoization involves storing the results of expensive function calls and reusing them when the same inputs occur again. Here's how you can implement the Stair Climbing Problem with memoization:

def climbStairsMemo(n, memo):
    if n <= 2:
        return n
    if n in memo:
        return memo[n]
    memo[n] = climbStairsMemo(n - 1, memo) + climbStairsMemo(n - 2, memo)
    return memo[n]

def climbStairsTopDown(n):
    memo = {}
    return climbStairsMemo(n, memo)

In this code, we use a dictionary called memo to store the results of subproblems. Before calculating the number of ways to reach the nth step, we check if it's already in the memo. If it is, we simply return the stored value. Otherwise, we calculate it, store it in the memo, and return it.

The time complexity of this approach is O(n) because each subproblem is solved only once. The space complexity is also O(n) because we need to store the results of n subproblems in the memo.

Bottom-Up (Tabulation)

The bottom-up approach involves building a table of results from the smallest subproblems to the largest. Here's how you can implement the Stair Climbing Problem with tabulation:

def climbStairsBottomUp(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

In this code, we create an array called dp to store the number of ways to reach each step. We initialize dp[1] to 1 and dp[2] to 2. Then, we iterate from 3 to n, calculating the number of ways to reach each step based on the number of ways to reach the previous two steps.

The time complexity of this approach is O(n) because we iterate through the array once. The space complexity is also O(n) because we need to store the results of n subproblems in the dp array.

Optimizing Space Complexity

While the bottom-up approach is already quite efficient, we can further optimize it by reducing the space complexity. Notice that we only need the values of the previous two steps to calculate the current step. This means we don't need to store the entire dp array. Instead, we can use two variables to keep track of the previous two values.

Here's the optimized code:

def climbStairsOptimized(n):
    if n <= 2:
        return n
    one_step_before = 2
    two_steps_before = 1
    for i in range(3, n + 1):
        current = one_step_before + two_steps_before
        two_steps_before = one_step_before
        one_step_before = current
    return current

In this code, one_step_before stores the number of ways to reach the (i-1)th step, and two_steps_before stores the number of ways to reach the (i-2)th step. We update these variables in each iteration, so we always have the values we need.

The time complexity of this approach is still O(n), but the space complexity is now O(1) because we only use two variables.

Conclusion

The Stair Climbing Problem is a fantastic way to learn about dynamic programming. We've explored three different approaches: recursion, dynamic programming with memoization, and dynamic programming with tabulation. We also optimized the space complexity of the bottom-up approach.

Remember, the key to solving dynamic programming problems is to identify the optimal substructure and overlapping subproblems. Once you understand these properties, you can apply dynamic programming techniques to solve a wide range of optimization problems.

So, next time you encounter the Stair Climbing Problem or a similar challenge, you'll be well-equipped to tackle it like a pro. Happy coding, and I'll catch you in the next one!