Blind 75 - problem 15 : Climbing Stairs

Climbing Stairs - LeetCode Solution & Explanation

Problem Statement

The Climbing Stairs problem is a classic Dynamic Programming (DP) question found on LeetCode.

Problem:
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 reach the top?

Constraints:

• 1 <= n <= 45

Example 1:

Input: n = 2
Output: 2
Explanation: 1 step + 1 step OR 2 steps at once.

Example 2:

Input: n = 3
Output: 3
Explanation: 
1. 1 step + 1 step + 1 step  
2. 1 step + 2 steps  
3. 2 steps + 1 step  

---

Optimal Approach: Fibonacci Dynamic Programming (Bottom-Up)

This problem follows the Fibonacci sequence, where:

• dp[i] = dp[i-1] + dp[i-2]
• Base cases: dp[1] = 1, dp[2] = 2

Since we can reach n from either n-1 or n-2, the solution follows:

$$f(n) = f(n-1) + f(n-2)$$

Optimized Approach Using Variables (O(n) → O(1) Space)

Instead of maintaining an entire array, we only need two variables to store the last two results.

---

LeetCode-Compatible C++ Solution

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        int first = 1, second = 2;
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)

---

Step-by-Step Explanation

1. Base Cases:

   • If n == 1, return 1 since there's only one way to climb.
   • If n == 2, return 2 (either 1+1 or 2).

2. Loop through 3 to n:

   • Calculate third = first + second (Fibonacci logic).
   • Move variables: first = second and second = third.

3. Return the final value of second, which holds the answer.

---

Dry Run (Execution Steps)

Let's take n = 5 as an example:

Step	first	second	third (new value)
Init	1	2	-
i=3	1	2	3
i=4	2	3	5
i=5	3	5	8

Output: 8 (Ways to climb 5 steps)

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Recursion)	O(2^n)	O(n)	Exponential growth, very slow
Memoization (Top-Down DP)	O(n)	O(n)	Extra space used for recursion stack
Tabulation (Bottom-Up DP Array)	O(n)	O(n)	Requires O(n) space
Optimized DP (2 Variables)	O(n)	O(1)	Best balance of time & space

---

Best Solution & Why?

The optimized DP solution using two variables is the best because: ✅ Linear Time Complexity (O(n)) – Efficient for large n.
✅ Constant Space Complexity (O(1)) – No extra array or recursion stack.
✅ Easy Implementation – Simple loop and variable swaps.

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
Brute Force Recursion	O(2^n)	O(n)
Memoization (Top-Down DP)	O(n)	O(n)
Bottom-Up DP (Array)	O(n)	O(n)
Optimized DP (2 Variables)	O(n)	O(1)

---

Conclusion

• Best Approach: Optimized DP with O(n) time and O(1) space.
• Why? Avoids recursion overhead and extra memory.
• Similar Problems to Practice:
  1. Fibonacci Number LeetCode #509
  2. Min Cost Climbing Stairs LeetCode #746
  3. House Robber LeetCode #198