LeetCode 70: Climbing Stairs - All Solutions Explained

Problem Statement

The Climbing Stairs problem, LeetCode 70, is an easy-difficulty challenge where you’re given an integer n representing the number of stairs in a staircase. You can climb either 1 or 2 stairs at a time, and your task is to find the number of distinct ways to reach the top. This is a classic combinatorial problem that builds on dynamic programming concepts.

Constraints

• 1≤n≤451 \leq n \leq 451≤n≤45

Example

Copy codeInput: n = 2
Output: 2
Explanation:
- 1 + 1 = 2
- 2 = 2
There are 2 ways to climb 2 stairs.

Copy codeInput: n = 3
Output: 3
Explanation:
- 1 + 1 + 1 = 3
- 1 + 2 = 3
- 2 + 1 = 3
There are 3 ways to climb 3 stairs.

Copy codeInput: n = 1
Output: 1
Explanation: Only one way: 1 step.

Understanding the Problem

We need to compute the number of distinct ways to climb n stairs using steps of 1 or 2. Key points:

• This resembles the Fibonacci sequence: to reach step n, you can come from n-1 (1 step) or n-2 (2 steps).
• The recurrence relation is ways(n)=ways(n−1)+ways(n−2)ways(n) = ways(n-1) + ways(n-2)ways(n)=ways(n−1)+ways(n−2).
• We need an efficient solution for nnn up to 45. Let’s explore two solutions:

1. Dynamic Programming (Iterative) : Space-optimized and efficient (best solution).
2. Recursive with Memoization : Intuitive but less optimal without optimization.

Solution 1: Dynamic Programming (Iterative) (Best Solution)

Intuition

The number of ways to climb n stairs follows a pattern similar to Fibonacci: the ways to reach n is the sum of ways to reach n-1 and n-2. Instead of using a full DP array, we can use two variables to track the previous two values, optimizing space.

How It Works

• Base cases:
  • n=1n=1n=1: 1 way.
  • n=2n=2n=2: 2 ways.
• For n≥3n \geq 3n≥3:
  • Initialize prev = 1 (ways for 1 stair), curr = 2 (ways for 2 stairs).
  • Iterate from 3 to n, updating prev and curr as the sum of the previous two values.
• Return the final curr.

Step-by-Step Example

For n = 4:

• n=1n=1n=1: 1 way.
• n=2n=2n=2: 2 ways.
• n=3n=3n=3: prev=1, curr=2 → next=1+2=3.
• n=4n=4n=4: prev=2, curr=3 → next=2+3=5.
• Result: 5 ways.

Python Code (Best Solution)

Copy codedef climbStairs(n):
    if n <= 1:
        return 1
    if n == 2:
        return 2
    
    prev, curr = 1, 2
    for i in range(3, n + 1):
        prev, curr = curr, prev + curr
    
    return curr

# Test cases
print(climbStairs(2))  # Output: 2
print(climbStairs(3))  # Output: 3
print(climbStairs(1))  # Output: 1

Detailed Walkthrough

• Base Cases : Handle n=1n=1n=1 and n=2n=2n=2 directly.
• Iteration : For n=4n=4n=4:
  • i=3: prev=1, curr=2 → curr=3.
  • i=4: prev=2, curr=3 → curr=5.
• Result : Matches the Fibonacci-like pattern (1, 2, 3, 5, 8, ...).

Complexity

• Time Complexity : O(n). Single pass through the range.
• Space Complexity : O(1). Only two variables.

Why It’s the Best

• Optimal time and space complexity.
• Simple and efficient implementation.
• Interview-preferred for its elegance and optimization.

Solution 2: Recursive with Memoization

Intuition}

Recursively compute the ways to reach n by summing the ways to reach n-1 and n-2, using memoization to avoid recomputing values. This reflects the problem’s recursive nature but requires extra space.

How It Works

• Define a recursive function with a memoization cache.
• Base cases: n=1n=1n=1 returns 1, n=2n=2n=2 returns 2.
• Recursive case: ways(n)=ways(n−1)+ways(n−2)ways(n) = ways(n-1) + ways(n-2)ways(n)=ways(n−1)+ways(n−2).
• Store results in a memo dictionary to prevent exponential growth.

Python Code

Copy codedef climbStairs(n):
    memo = {}}
    
    def dp(steps):
        if steps <= 1:
            return 1
        if steps == 2:
            return 2
        if steps in memo:
            return memo[steps]
        
        memo[steps] = dp(steps - 1) + dp(steps - 2)
        return memo[steps]
    
    return dp(n)

# Test cases
print(climbStairs(2))  # Output: 2
print(climbStairs(3))  # Output: 3
print(climbStairs(1))  # Output: 1

Detailed Walkthrough

• For n=4n=4n=4:
  • dp(4)=dp(3)+dp(2)dp(4) = dp(3) + dp(2)dp(4)=dp(3)+dp(2).
  • dp(3)=dp(2)+dp(1)=2+1=3dp(3) = dp(2) + dp(1) = 2 + 1 = 3dp(3)=dp(2)+dp(1)=2+1=3.
  • dp(2)=2dp(2) = 2dp(2)=2.
  • dp(4)=3+2=5dp(4) = 3 + 2 = 5dp(4)=3+2=5.
• Memoization : Stores each computed value (e.g., {2: 2, 3: 3, 4: 5}).

Complexity

• Time Complexity : O(n). Each step computed once.
• Space Complexity : O(n). Memoization dictionary.

Pros and Cons

• Pros : Intuitive recursive solution.
• Cons : Uses more space than iterative DP.

Comparison of Solutions

Edge Cases to Consider

1. n = 1 : 1 way.
2. n = 2 : 2 ways.
3. Large n : n=45n=45n=45, still efficient (1134903170 ways).
4. Minimum n : n=1n=1n=1 per constraints.

Final Thoughts

• Iterative DP : The best solution —fast, space-efficient, and straightforward.
• Recursive Memoization : Useful for understanding but less optimal. Master the iterative DP method for its optimization brilliance. Try extending it to k-step jumps as a follow-up!