Climbing Stairs Problem

Problem Description

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?

Brute Force Solution (Recursion)

A naive approach is to use recursion. We can define a recursive function climbStairs(n) that returns the number of ways to climb n stairs. The base cases are:

• climbStairs(0) = 1 (one way to climb 0 stairs: do nothing)
• climbStairs(1) = 1 (one way to climb 1 stair: take 1 step)

For n > 1, the number of ways to climb n stairs is the sum of the number of ways to climb n-1 stairs (by taking 1 step from n-1) and the number of ways to climb n-2 stairs (by taking 2 steps from n-2).

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

Time Complexity: O(2ⁿ) - Exponential, due to overlapping subproblems.

Space Complexity: O(n) - Due to the recursion depth.

Optimal Solution (Dynamic Programming)

The recursive solution is inefficient because it recalculates the same values multiple times. We can use dynamic programming to store the results of subproblems and avoid recalculation.

We can create an array dp of size n+1, where dp[i] stores the number of ways to climb i stairs. The base cases are dp[0] = 1 and dp[1] = 1. Then, for i > 1, dp[i] = dp[i-1] + dp[i-2].

def climbStairs_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]

Time Complexity: O(n) - Linear, as we iterate through the array once.

Space Complexity: O(n) - Linear, due to the dp array.

Further Optimization (Constant Space)

We can observe that we only need the previous two values to calculate the current value. Therefore, we can reduce the space complexity to O(1) by storing only the previous two values.

def climbStairs(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

Time Complexity: O(n) - Linear.

Space Complexity: O(1) - Constant.

Edge Cases

• n = 1: Returns 1
• n = 2: Returns 2
• n = 3: Returns 3

Summary

The most optimal solution uses dynamic programming with constant space to calculate the number of distinct ways to climb the stairs. The time complexity is O(n), and the space complexity is O(1).