1. Understanding the Problem

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 step or 2 steps. Your task is to calculate in how many distinct ways you can climb to the top.

The Core Constraint (The Trap):

It is incredibly tempting to simulate every single possible path using recursion (a decision tree). However, as the staircase gets taller, the number of possible combinations explodes exponentially. Doing the exact same calculation multiple times will trigger a massive "Time Limit Exceeded" error.

2. The Naive Approach: Pure Recursion

The most intuitive way to solve this is to think backwards from the top step (step n). How could you have arrived at step n? You either took a 1-step jump from step n-1, or a 2-step jump from step n-2. Therefore, the total ways to reach step n is simply the sum of the ways to reach step n-1 and step n-2.

Trade-off Analysis

While this logic mathematically works perfectly, it is a performance nightmare without optimization (memoization):

• Time Complexity: O(2^N) — Every function call branches into two more function calls. If you want to find the ways to reach step 40, your program will have to calculate millions of overlapping redundant branches.
• Space Complexity: O(N) — The recursive call stack will go as deep as the number of stairs, consuming significant memory.

3. The Optimal Approach: Bottom-Up Dynamic Programming (O(1) Space)

To pass a senior-level technical interview, we want to achieve an O(N) time complexity and an O(1) space complexity. If you look closely at the recursive logic (ways[n] = ways[n-1] + ways[n-2]), you might recognize a famous mathematical sequence: The Fibonacci Sequence.

Instead of starting at the top and branching wildly downwards, we start at the bottom and work our way up. If we know the ways to reach step 1 and step 2, we can easily calculate step 3. Once we have step 3, we can drop step 1 from our memory and just use step 2 and step 3 to calculate step 4.

We only ever need to remember the last two steps we calculated. We can discard all previous history, entirely eliminating the need for an array or a deep recursive stack!

4. The Logic Step-by-Step

1. Base Cases: If n is 1, there is only 1 way to climb it. Return 1 immediately. If n is 2, there are 2 ways to climb it (1+1 or 2).
2. Initialize Trackers: Create two variables to represent the last two steps. Set prev1 = 1 (ways to reach step 1) and prev2 = 2 (ways to reach step 2).
3. Iterate to the Top: Create a loop starting from step 3 up to step n.
   • Calculate the ways to reach the current step: current = prev1 + prev2.
   • Shift your memory forward for the next iteration: The old prev2 becomes the new prev1, and the current step becomes the new prev2.
4. When the loop finishes, your current variable (or prev2) will hold the total number of ways to reach step n.

5. Complexity Analysis

• Time Complexity: O(N) — We iterate through the stairs exactly one time, from step 3 to step n. This is a massive leap from O(2^N).
• Space Complexity: O(1) — We only use a few integer variables (prev1, prev2, and current) to track our state. We have successfully avoided arrays and recursive call stacks, achieving constant space!

6. Code Implementations

Expand the sections below to see the optimal O(1) space "Fibonacci DP" implementations across different languages.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
            
        prev1 = 1
        prev2 = 2
        
        for i in range(3, n + 1):
            current = prev1 + prev2
            
            # Shift pointers forward for the next iteration
            prev1 = prev2
            prev2 = current
            
        return prev2

class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        
        int prev1 = 1;
        int prev2 = 2;
        
        for (int i = 3; i <= n; i++) {
            int current = prev1 + prev2;
            
            // Shift pointers forward for the next iteration
            prev1 = prev2;
            prev2 = current;
        }
        
        return prev2;
    }
}

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        
        int prev1 = 1;
        int prev2 = 2;
        
        for (int i = 3; i <= n; i++) {
            int current = prev1 + prev2;
            
            // Shift pointers forward for the next iteration
            prev1 = prev2;
            prev2 = current;
        }
        
        return prev2;
    }
};

7. Conclusion: You Are Ready

Congratulations, you have just crossed the bridge into Dynamic Programming! Understanding that complex recursion can often be flipped upside down into a simple, iterative "bottom-up" approach is a critical milestone for any software engineer. By realizing that you only needed the last two calculations, you transformed a memory-heavy array solution into an elegant O(1) state-machine. Keep this variable-shifting pattern in your mental toolkit, as it applies to many sequence and path-finding interview questions!