Climbing Stairs

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 1:

Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

Example 2:

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

Constraints: 1 <= n <= 45

# Climbing Stairs

This problem is a classic example of dynamic programming. We are given a staircase with `n` steps, and we can climb either 1 or 2 steps at a time. The goal is to find the number of distinct ways to reach the top.

## 1. Brute Force (Recursion)

A naive approach is to use recursion. The base cases are:

*   If `n` is 0, there is 1 way (we are already at the top).
*   If `n` is negative, there are 0 ways (invalid).

For `n > 0`, the number of ways is the sum of ways to reach `n-1` (taking 1 step) and `n-2` (taking 2 steps).

```python
def climb_stairs_recursive(n):
    if n == 0:
        return 1
    if n < 0:
        return 0
    return climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2)

# Example usage
n = 5
print(f"Number of ways to climb {n} stairs (recursive): {climb_stairs_recursive(n)}")

Diagram:

Consider n = 4.

climb_stairs(4)
├── climb_stairs(3)
│   ├── climb_stairs(2)
│   │   ├── climb_stairs(1)
│   │   │   ├── climb_stairs(0) -> 1
│   │   │   └── climb_stairs(-1) -> 0
│   │   ├── climb_stairs(0) -> 1
│   ├── climb_stairs(1)
│   │   ├── climb_stairs(0) -> 1
│   │   └── climb_stairs(-1) -> 0
├── climb_stairs(2)
│   ├── climb_stairs(1)
│   │   ├── climb_stairs(0) -> 1
│   │   └── climb_stairs(-1) -> 0
│   ├── climb_stairs(0) -> 1

2. Optimal Solution (Dynamic Programming)

The recursive solution has overlapping subproblems. We can use dynamic programming to store the results of subproblems and avoid recomputation.

We can use an array dp where dp[i] stores the number of ways to reach step i. The base cases are dp[0] = 1 and dp[1] = 1. Then, dp[i] = dp[i-1] + dp[i-2].

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

# Example usage
n = 5
print(f"Number of ways to climb {n} stairs (DP): {climb_stairs_dp(n)}")

We can further optimize the space complexity by using only two variables to store the previous two values instead of an entire array.

def climb_stairs_optimized(n):
    if n <= 1:
        return 1
    a = 1
    b = 1
    for i in range(2, n + 1):
        temp = a + b
        a = b
        b = temp
    return b

# Example usage
n = 5
print(f"Number of ways to climb {n} stairs (optimized): {climb_stairs_optimized(n)}")

3. Big O Run-time Analysis

• Recursive (Brute Force): O(2^n). Each call branches into two more calls. This results in exponential time complexity because we recalculate results many times. For each n, we are doing the work of 2^(n-1) + 2^(n-2) + ... + 2^0, which ends up being O(2^n).
• Dynamic Programming: O(n). The loop iterates n times to fill the dp array.
• Optimized Dynamic Programming: O(n). The loop iterates n times.

4. Big O Space Usage Analysis

• Recursive (Brute Force): O(n). The depth of the recursion tree can go up to n in the worst case, thus requiring O(n) space on the call stack.
• Dynamic Programming: O(n). We use an array dp of size n+1 to store intermediate results.
• Optimized Dynamic Programming: O(1). We only use a constant number of variables (a, b, temp) regardless of the input size n.

5. Edge Cases

• n = 0: The problem statement says 1 <= n <= 45, but for completeness, if n is 0, there is 1 way (do nothing).
• n = 1: There is 1 way (take one step).
• n = 2: There are 2 ways (1+1 or 2).
• Large n: The problem statement limits n to 45. With recursion, large n will cause stack overflow or time limit exceeded. Dynamic programming avoids these issues.