🌱 Keegan's Digital Garden

70. Climbing Stairs

2 min read

📝 Problem Details

climbing a staircase and it takes n steps to reach the top each time you can climb 1 or 2 steps in how many distinct ways can you climb to the top

💭What Were My Initial Thoughts?

1. can it be broken into subproblems? 
- i would say yes, the number of ways it we can get to step 1 can be used to contribute to how we compute how many ways we can get to step n 

2. choose top-down vs. bottom-up 
- based on my above assumption, i would say that a bottom up approach seems appropriate? 
- but maybe both approaches are viable here 

3. define dp state: 
- i would say that dp[i] represents the number of ways you can climb to i stairs 
- where the dp table would be a 1d vector with n elements 

4. transition formula: 
- since we know that at each step we can either move 1 or 2 steps (as long as its in bounds), we could possibly sum the values in the two previous steps to get the number of ways for this current step 
- dp[i] = dp[i-1] + dp[i-2] 

5. optimize for space - since we only need the last two steps, we dont need the dp table to hold all n steps

💡 Explanation of Solution

We can implement a space optimized approach
Instead of storing all `dp[i]` values, **we only need the last two steps** (`dp[i-1]` and `dp[i-2]`).
We can **reduce the space complexity from O(n) → O(1)** by using two variables.

⌛ Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        int prev1 = 2, prev2 = 1, curr;
        for (int i = 3; i <= n; i++) {
            curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        
        return prev1;
    }
};

Graph View