Climbing Stairs

Problem

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

Solution

Approach 1: Dynamic Programming (Bottom-Up)

The key insight is that to reach step n, you can come from step n-1 (take 1 step) or step n-2 (take 2 steps). So dp[n] = dp[n-1] + dp[n-2].

Implementation

class Solution:
    def climbStairs(self, n: int) -> int:
        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]

Approach 2: Space-Optimized DP

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        prev2 = 1  # ways to reach step 1
        prev1 = 2  # ways to reach step 2

        for i in range(3, n + 1):
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current

        return prev1

Approach 3: Recursion with Memoization (Top-Down)

class Solution:
    def climbStairs(self, n: int) -> int:
        memo = {}

        def dp(i):
            if i <= 2:
                return i
            if i in memo:
                return memo[i]

            memo[i] = dp(i-1) + dp(i-2)
            return memo[i]

        return dp(n)

Complexity Analysis

Bottom-Up DP:

Time Complexity: O(n), single pass through all steps.
Space Complexity: O(n) for dp array, O(1) for space-optimized version.

Top-Down DP:

Time Complexity: O(n), each subproblem solved once.
Space Complexity: O(n) for memoization and recursion stack.

Key Insights

Fibonacci Pattern: This is essentially the Fibonacci sequence. The number of ways follows the same recurrence relation.
Optimal Substructure: The number of ways to reach step n depends on the number of ways to reach steps n-1 and n-2.
Base Cases: There’s 1 way to reach step 1, and 2 ways to reach step 2 (1+1 or 2).
Space Optimization: Since we only need the previous two values, we can use O(1) space instead of O(n).
No Repeated Subproblems: Each step is computed once and reused, making DP efficient.