Climbing Stairs - DP to O(1) Space

📚 Table of Contents

Problem Statement
Real-World Analogy
Key Insights
Solution Approaches
Step-by-Step Walkthrough
Complexity Analysis
Edge Cases
Test Cases
Interview Tips
Key Takeaways

📋 Problem Statement

At each move you can climb either 1 step or 2 steps. Count the number of distinct sequences that land exactly on step n.

Examples

Example 1:
Input: n = 2
Output: 2
Ways: [1+1], [2]

Example 2:
Input: n = 3
Output: 3
Ways: [1+1+1], [1+2], [2+1]

Constraints

1 <= n <= 45

🎯 Real-World Analogy

Building Routes on a Stair Map

To reach step i, your final move must come from either step i-1 (taking 1 step) or step i-2 (taking 2 steps).

So total ways to step i is the sum of ways to the two previous steps. That is exactly Fibonacci recurrence with different base values.

💡 Key Insights

Recurrence: ways[i] = ways[i-1] + ways[i-2].
Base cases: ways[1] = 1, ways[2] = 2.
Top-down recursion repeats work; DP avoids recomputation.
Only previous two states are needed, so O(1) space is enough.
This is the canonical interview introduction to dynamic programming.

💻 Solution Approaches

Approach 1: Naive Recursion

Time: O(2^N) | Space: O(N) recursion stack

Direct recurrence without memoization causes repeated calls and exponential blow-up.

Approach 2: Bottom-Up DP with O(1) Space (Recommended)

Time: O(N) | Space: O(1)

Iterate once, carrying only two previous values.

Python Implementation

          def climb_stairs(n: int) -> int:
    """
    Count ways to reach step n with jumps of 1 or 2.

    Time: O(N)
    Space: O(1)
    """
    if n <= 2:
        return n

    prev2 = 1  # ways for step 1
    prev1 = 2  # ways for step 2

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

    return prev1
        

JavaScript Implementation

          function climbStairs(n) {
  /**
   * Count ways to reach step n with jumps of 1 or 2.
   *
   * Time: O(N)
   * Space: O(1)
   */
  if (n <= 2) return n;

  let prev2 = 1;
  let prev1 = 2;

  for (let step = 3; step <= n; step++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }

  return prev1;
}
        

🔍 Step-by-Step Walkthrough

Trace n = 5:

Base: ways(1)=1, ways(2)=2

            Step 3: ways(3) = ways(2) + ways(1) = 2 + 1 = 3
          
            Step 4: ways(4) = ways(3) + ways(2) = 3 + 2 = 5
          
            Step 5: ways(5) = ways(4) + ways(3) = 5 + 3 = 8

⚡ Complexity Analysis

Time Complexity: O(N)

We compute each step once from 3 to n.

Space Complexity: O(1)

Only three scalar variables are used regardless of n.

🔧 Edge Cases

n = 1 -> 1
n = 2 -> 2
Upper bound n = 45 (still safe in 32-bit integer)
Ensure no off-by-one in loop bounds

🧪 Test Cases

Python

          def test_climb_stairs():
    assert climb_stairs(1) == 1
    assert climb_stairs(2) == 2
    assert climb_stairs(3) == 3
    assert climb_stairs(4) == 5
    assert climb_stairs(5) == 8
    assert climb_stairs(10) == 89

    print("✅ all tests passed")
        

JavaScript

          function testClimbStairs() {
  console.assert(climbStairs(1) === 1, "test 1");
  console.assert(climbStairs(2) === 2, "test 2");
  console.assert(climbStairs(3) === 3, "test 3");
  console.assert(climbStairs(4) === 5, "test 4");
  console.assert(climbStairs(5) === 8, "test 5");
  console.assert(climbStairs(10) === 89, "test 6");

  console.log("✅ all tests passed");
}
        

💼 Interview Tips

Name the recurrence before coding.
Give both DP-array and O(1)-space versions; implement O(1)-space one.
Show base cases explicitly for n=1 and n=2.
Mention relation to Fibonacci to communicate intuition quickly.
For follow-up, discuss generalized step sizes {1,2,3,...}.

🎓 Key Takeaways

Climbing Stairs is recurrence-first thinking: define relation + base cases.
DP often reduces to keeping only the minimal rolling state.
This pattern appears in many "count ways" combinatorics problems.

← Back to All Algorithms