Skip to main content

🪜 Climbing Stairs - The Discovery Journey

The Problem (Quick Glance)​

LC 70: Climbing Stairs

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

Initial Observations:

  • This is a counting problem - count distinct ways
  • At each step, we have 2 choices: climb 1 or 2 steps
  • The answer depends on ways to reach previous steps
  • This is Fibonacci in disguise!

1. My First Approach: Thinking Recursively​

COMING SOON

This section will explore:

  • How to reach step n? From step (n-1) or step (n-2)
  • Pure recursive formulation
  • Why this creates a Fibonacci-like structure
  • Visualization of the recursion tree

The Key Insight:

To reach step n:
- Come from step (n-1) and take 1 step
- Come from step (n-2) and take 2 steps

ways(n) = ways(n-1) + ways(n-2)

2. Why This is Fibonacci​

THE CONNECTION

Climbing Stairs = Fibonacci Sequence

n = 1 → 1 way:  [1]
n = 2 → 2 ways: [1,1] or [2]
n = 3 → 3 ways: [1,1,1] or [1,2] or [2,1]
n = 4 → 5 ways: ...
n = 5 → 8 ways: ...

Compare to Fibonacci:
F(1) = 1
F(2) = 2
F(3) = 3
F(4) = 5
F(5) = 8

Same sequence! (with slightly different base cases)

Why?

  • To reach step n, you combine ways from steps (n-1) and (n-2)
  • This is exactly how Fibonacci is defined!

3. Solution Evolution​

COMING SOON

We'll build through these approaches:

Approach 1: Pure Recursion​

public int climbStairs(int n) {
    if (n <= 2) return n;
    return climbStairs(n-1) + climbStairs(n-2);
}
  • Time: O(2^n) - Exponential!
  • Space: O(n) - Recursion depth

Approach 2: Memoization (Top-Down DP)​

  • Add memo array to cache results
  • Time: O(n), Space: O(n)

Approach 3: Bottom-Up DP​

  • Build table iteratively
  • Time: O(n), Space: O(n)

Approach 4: Space-Optimized​

  • Only track last 2 values
  • Time: O(n), Space: O(1)

4. The Mental Model​

UNDERSTANDING THE PROBLEM

Think backwards:

To reach step 5:
├── From step 4 (take 1 step) → ways(4) paths
└── From step 3 (take 2 steps) → ways(3) paths

Total ways(5) = ways(4) + ways(3)

Building forward:

Step 0: 1 way (stay at ground)
Step 1: 1 way [1]
Step 2: 2 ways [1,1] or [2]
Step 3: ways(2) + ways(1) = 2 + 1 = 3
Step 4: ways(3) + ways(2) = 3 + 2 = 5
Step 5: ways(4) + ways(3) = 5 + 3 = 8

5. Complete Implementation (Preview)​

// Space-Optimized Solution - O(n) time, O(1) space
public int climbStairs(int n) {
    if (n <= 2) return n;

    int prev2 = 1;  // ways(1)
    int prev1 = 2;  // ways(2)

    for (int i = 3; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

6. Key Differences from Similar Problems​

DON'T CONFUSE WITH

Climbing Stairs (LC 70) vs Min Cost Climbing Stairs (LC 746):

AspectClimbing StairsMin Cost Climbing Stairs
Question"How many ways?""What's minimum cost?"
OperationCount (sum)Minimize (min)
Formulaways[i] = ways[i-1] + ways[i-2]cost[i] = min(cost[i-1], cost[i-2]) + ...
Base caseways[1]=1, ways[2]=2cost[0]=0, cost[1]=0

Both use Fibonacci-like structure, but different operations!

7. Why This Problem Matters​

FOUNDATIONAL PROBLEM

Climbing Stairs teaches:

  1. ✅ How to identify recursive structure
  2. ✅ The Fibonacci pattern in disguise
  3. ✅ Counting problems vs optimization problems
  4. ✅ The full DP evolution: recursion → memoization → DP → space optimization

This is one of the first DP problems you should master!

It appears in variations across many interview problems:

  • Decode Ways (LC 91) - Similar structure with conditions
  • House Robber (LC 198) - Modified with constraints
  • Many counting problems use this pattern

Coming Soon​

MORE CONTENT COMING

We'll add:

  • Complete recursive solution with tree visualization
  • Memoized solution with execution traces
  • Bottom-up DP with step-by-step build
  • Mathematical formula approach
  • Detailed complexity analysis
  • Common mistakes and edge cases
  • Practice variations

Key Takeaways​

REMEMBER
  1. ✅ Climbing Stairs = Fibonacci in disguise
  2. ✅ Pattern: ways(n) = ways(n-1) + ways(n-2)
  3. ✅ Counting problem (sum) vs optimization problem (min/max)
  4. ✅ Perfect for learning DP progression
  5. ✅ Foundation for many other DP problems

Master this problem - it's a gateway to understanding DP!

Quick Solution Reference​

// Optimal Solution
public int climbStairs(int n) {
    if (n <= 2) return n;

    int prev2 = 1, prev1 = 2;

    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }

    return prev1;
}

// Time: O(n), Space: O(1)