14. Climbing Stairs

Difficulty:EasyPattern:Fibonacci DPTime:O(n)Space:O(1)

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?

How It Works & Algorithmic Design

Follows Fibonacci Sequence State Transition:

Base Cases: To reach step 1 = 1 way. Step 2 = 2 ways (1+1, 2).
Recurrence: ways(n) = ways(n - 1) + ways(n - 2) (you can reach step $n$ from step $n-1$ taking 1 step or step $n-2$ taking 2 steps).
Space Optimization: Maintain two variables prev2 = 1, prev1 = 2 and compute iteratively.

Why This Approach Works Best

Iterative state tracking computes ways in $O(n)$ time using $O(1)$ extra space, avoiding $O(2^n)$ recursive stack overflow.

Example Walkthrough

Input: n = 3

3 steps.

Ways: 1+1+1, 1+2, 2+1

Total 3 distinct paths.

Output: 3

Number of ways.

Answer: Climbing Stairs DP implementation

function climbStairs(n) {
  if (n <= 2) return n;
  let prev2 = 1, prev1 = 2;
  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

💡 Compute step combinations iteratively using two tracking variables.

Key Takeaways

Matches Fibonacci recurrence relation $F(n) = F(n-1) + F(n-2)$.
Optimized to $O(1)$ memory by tracking only the last two values.
Runs in linear $O(n)$ time.