Climbing Stairs

• Difficulty: Easy
• Topics: Math, Dynamic Programming, Memoization
• Link: https://leetcode.com/problems/climbing-stairs/

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?

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

1. Problem Deconstruction

Technical Version:
Given integer n representing staircase steps, compute the cardinality of all possible sequences where each element ∈ {1,2} and the sum equals n.

Beginner Version:
Imagine you’re climbing stairs. You can take 1 step or leap 2 steps at once. How many different paths can you take to reach the top if there are n stairs?

Mathematical Formulation:
Let f(n) = number of distinct ways. Base cases:

• f(0) = 1 (empty sequence)
• f(1) = 1
  Recurrence:
  f(n) = f(n-1) + f(n-2) for n ≥ 2

Constraint Analysis:

1. 1 <= n <=45:
   • Upper limit 45 prevents exponential brute-force solutions (max 2^45 operations ≈ 3.5e13 → infeasible).
   • Edge Cases:
     • n=1 → single way (1 step).
     • n=45 requires O(n) time to avoid stack overflows from recursion.

---

2. Intuition Scaffolding

Analogies:

1. Real-World: Like decoding a lock with digits 1 and 2. How many combinations sum to n?
2. Gaming: RPG skill trees where you spend 1 or 2 points per level.
3. Math: Fibonacci sequence shifted by one (f(n) = Fib(n+1)).

Common Pitfalls:

1. Recursive Redundancy: Unmemoized recursion recalculates f(3) for f(5) and f(4).
2. Order Ignorance: Treating 1+2 and 2+1 as identical (they’re distinct paths).
3. Base Case Errors: Missing f(0)=1 leads to incorrect f(2)=1 instead of 2.
4. Overcounting: Including steps beyond 2 (e.g., 3-step jumps).
5. Space Inefficiency: Storing entire DP array when only last two values are needed.

---

3. Approach Encyclopedia

Brute-Force (Recursive):

def climb_stairs(n):  
    if n <= 1: return 1  
    return climb_stairs(n-1) + climb_stairs(n-2)  

Complexity:

• Time: O(2^n) → Each call branches twice.
• Space: O(n) recursion depth.

Memoization (Top-Down DP):

from functools import lru_cache  
def climb_stairs(n):  
    @lru_cache(maxsize=None)  
    def dfs(i):  
        if i <= 1: return 1  
        return dfs(i-1) + dfs(i-2)  
    return dfs(n)  

Complexity:

• Time: O(n) → Each f(i) computed once.
• Space: O(n) for cache + recursion stack.

Iterative (Bottom-Up DP):

def climb_stairs(n):  
    if n == 1: return 1  
    a, b = 1, 1  
    for _ in range(n-1):  
        a, b = b, a + b  
    return b  

Complexity:

• Time: O(n) → Single loop.
• Space: O(1) → Two variables.

Matrix Exponentiation (Advanced):
Leverage [[1,1],[1,0]]^n for O(log n) time.

# Implementation omitted for brevity  

Complexity:

• Time: O(log n) via exponentiation by squaring.
• Space: O(1).

Visualization:

n=4:  
Step 0: 1 way (stay)  
Step 1: 1 (1)  
Step 2: 1+1=2  
Step 3: 2+1=3  
Step 4: 3+2=5  
Paths: 1111, 112, 121, 211, 22  

---

4. Code Deep Dive

Optimal Code (Iterative):

def climb_stairs(n):  
    a, b = 1, 1  
    for _ in range(n-1):  
        a, b = b, a + b  
    return b  

Line-by-Line:

1. a, b = 1, 1: Initialize base cases f(0)=1, f(1)=1.
2. for _ in range(n-1): Loop n-1 times to reach f(n).
3. a, b = b, a + b: Update a to previous b (f(i-1)), b to f(i).

Edge Case Handling:

• n=1: Loop doesn’t run → returns b=1.
• n=2: After 1 iteration → b=2.

---

5. Complexity War Room

Hardware Analysis:

• For n=45: 45 iterations → ~45 CPU cycles (negligible). Memory: 2 integers (8 bytes).

Approach Comparison:

Approach	Time	Space	Readability	Interview Viability
Brute-Force	O(2ⁿ)	O(n)	7/10	❌
Memoization	O(n)	O(n)	8/10	✅
Iterative DP	O(n)	O(1)	9/10	✅
Matrix Power	O(log n)	O(1)	5/10	✅ (Advanced)

---

6. Pro Mode Extras

Variants:

1. 3-Step Jumps: f(n) = f(n-1) + f(n-2) + f(n-3).
2. k-Step Jumps: Precompute all prior k terms (DP array).
3. LC 746 Min Cost Climbing Stairs: Add cost minimization.

Interview Cheat Sheet:

• Key Insight: Recurrence mirrors Fibonacci.
• First Mention: Time/Space of iterative approach (O(n)/O(1)).
• Test Cases: n=1, n=2, n=4 (covers base and transition).