Climbing Stairs Problem

The Climbing Stairs problem is a classic example of a combinatorial problem that can be solved using several different techniques. In this article, we’ll explore how to efficiently solve the problem using dynamic programming, recursion, and understanding the relationship to the Fibonacci sequence.

Problem Description

In the Climbing Stairs problem, you're given a staircase with n steps. At each step, you can either climb 1 step or 2 steps. The goal is to determine how many distinct ways you can reach the top of the staircase.

Mathematical Foundation: Fibonacci Sequence

This problem can be mapped to the Fibonacci sequence, where the number of ways to reach step n is the sum of the ways to reach step n-1 and step n-2. Thus, if you know how to reach the previous two steps, you can easily calculate how to reach the current step.

Recursive Solution

Recursive Relation

Using recursion, the problem can be represented with the following recursive relation:

• ways(n) = ways(n-1) + ways(n-2)

Where ways(n) represents the number of ways to reach the nth step. The base cases are:

• ways(0) = 1: There is 1 way to stay at the ground level (do nothing).
• ways(1) = 1: There is 1 way to reach the first step.

Code for Recursive Solution

1
2
3
4
def climbStairs(n):
    if n <= 1:
        return 1
    return climbStairs(n - 1) + climbStairs(n - 2)

While this solution works, it’s highly inefficient due to repeated calculations. As a result, the time complexity of the recursive approach is O(2^n).

Dynamic Programming Approach

What is Dynamic Programming?

Dynamic programming (DP) is an optimization technique that solves problems by breaking them down into simpler subproblems and storing the results to avoid redundant calculations. It is especially useful for problems like Climbing Stairs that have overlapping subproblems.

DP Array

In a dynamic programming approach, we store the number of ways to reach each step in a dp array. The final answer will be stored in dp[n].

Code for Dynamic Programming Solution

1
2
3
4
5
6
7
8
9
10
11
def climbStairs(n):
    if n <= 1:
        return 1
    
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1
    
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

Time Complexity and Space Complexity

• Time Complexity: The time complexity of this approach is O(n) because we iterate through the steps once.
• Space Complexity: The space complexity is O(n) because we use a dp array of size n+1.

Optimizing Space Complexity

Space Optimization in Dynamic Programming

Although the dynamic programming solution works well, we can optimize the space complexity. Since we only need the previous two values to compute the current value, we can store only the last two values rather than the entire dp array.

Optimized Solution

1
2
3
4
5
6
7
8
9
10
11
12
def climbStairs(n):
    if n <= 1:
        return 1
    
    prev1, prev2 = 1, 1
    
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    
    return prev1

Time Complexity and Space Complexity

• Time Complexity: The time complexity remains O(n).
• Space Complexity: The space complexity is reduced to O(1) since we only use a constant amount of space.

Base Case and Recursive Nature

Base Case

In dynamic programming, it is important to handle the base case correctly. For the Climbing Stairs problem, the base cases are:

• ways(0) = 1: There is exactly 1 way to remain on the ground.
• ways(1) = 1: There is exactly 1 way to reach the first step.

These base cases are critical for initiating the calculation in both the recursive and dynamic programming solutions.

Conclusion

The Climbing Stairs problem provides a great opportunity to apply both recursion and dynamic programming techniques. While the recursive solution works, it is inefficient for larger values of n. Using dynamic programming allows us to optimize the solution, and further optimization is possible by reducing the space complexity to O(1).

By understanding the relationship between the Fibonacci sequence and the problem, we can efficiently compute the number of ways to reach the top of the staircase while minimizing time complexity and space complexity.