LeetCode Solution 70 - Climbing Stairs

Problem Statement

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?

Constraints:

• 1 <= n <= 45

Optimal Approach

The problem follows the Fibonacci sequence pattern. The number of ways to reach step n is the sum of the ways to reach steps n-1 and n-2.

Formula:

$dp[n] = dp[n-1] + dp[n-2]$ This can be solved using:

1. Recursion (inefficient)
2. Memoization (Top-Down DP)
3. Tabulation (Bottom-Up DP)
4. Space-Optimized DP (Best approach)

LeetCode-Compatible C++ Code Implementations

Dynamic Programming (Space-Optimized) - Best Approach

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 of Code

1. If n == 1, return 1 (only one way to climb).
2. Initialize first = 1 (1 step) and second = 2 (2 steps).
3. Use a loop from 3 to n, computing third = first + second.
4. Update first = second, second = third.
5. Return second as the final answer.

Dry Run / Execution Steps

Input: n = 5

Step	first	second	third
1	1	2	-
2	2	3	3
3	3	5	5
4	5	8	8
Result		8

Output: 8

Alternative Approaches & Why Not?

1. Recursive Approach

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        return climbStairs(n-1) + climbStairs(n-2);
    }
};

Time Complexity: $O(2^n)$ (Exponential, very slow) Space Complexity: $O(n)$ (Recursive stack)

❌ Why Not? Causes redundant calculations and time complexity explodes.

2. Memoization (Top-Down DP)

class Solution {
public:
    int dp[46] = {0};
    int climbStairs(int n) {
        if (n <= 2) return n;
        if (dp[n] > 0) return dp[n];
        return dp[n] = climbStairs(n-1) + climbStairs(n-2);
    }
};

Time Complexity: $O(n)$ Space Complexity: $O(n)$ (due to recursion depth and array)

✅ Better but still uses extra space.

3. Bottom-Up DP (Tabulation)

class Solution {
public:
    int climbStairs(int n) {
        int dp[46];
        dp[1] = 1, dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

Time Complexity: $O(n)$ Space Complexity: $O(n)$

✅ Efficient but can be further optimized in space.

Best Solution & Why It’s Best

The space-optimized approach (O(1)) is the best because:

• Uses only two variables instead of an array (O(n)).
• Runs in linear time (O(n)).

Comparison Table

Approach	Time Complexity	Space Complexity	Efficiency
Recursion	O(2^n)	O(n)	❌ Slow
Memoization DP	O(n)	O(n)	✅ Faster
Bottom-Up DP	O(n)	O(n)	✅ Good
Space-Optimized	O(n)	O(1)	🚀 Best

Complexity Analysis

Approach	Time Complexity	Space Complexity
Recursion	O(2^n)	O(n)
Memoization	O(n)	O(n)
Tabulation	O(n)	O(n)
Space-Optimized	O(n)	O(1)

Conclusion

• The best solution is the Space-Optimized DP (O(n) time, O(1) space).
• This problem is similar to Fibonacci Sequence, making it a great DP example.
• Practice More:
  • Fibonacci Number
  • House Robber
  • Min Cost Climbing Stairs

🚀 Mastering this problem strengthens your understanding of Dynamic Programming!