Climb Stairs

70.Climbing Stairs

Dynamic Programming

Math

Recursion

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?

Example:

Input:

n = 3

→

Output:

3

Algorithm:

1. Use Fibonacci sequence approach
2. Keep track of last two steps
3. Current step is sum of previous two
4. Optimize space by using variables

Complexity:

Time: O(n) | Space: O(1) for iterative, O(n) for recursive

Java Solution:

public int climbStairs(int n) {
    if (n <= 2) return n;  // Base cases

    int one = 1;  // n-1 step
    int two = 2;  // n-2 step
    int ans = 0;
    
    for (int i = 3; i <= n; i++) {
        ans = one + two;  // Current step is sum of previous two
        one = two;
        two = ans;
    }
    
    return ans;
}

// Recursive Solution with Memoization
public int climb(int n, Map<Integer, Integer> map) {
    if (n <= 2) return n;
    
    if (map.containsKey(n)) {
        return map.get(n);
    }
    
    int ways = climb(n - 1, map) + climb(n - 2, map);
    map.put(n, ways);
    return ways;
}

Python Solution:

def climbStairs(self, n: int) -> int:
    if n <= 2:
        return n
        
    one = 1
    two = 2
    
    for i in range(3, n + 1):
        curr = one + two
        one = two
        two = curr
        
    return two

C++ Solution:

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2) return n;
        
        int one = 1;
        int two = 2;
        int result;
        
        for(int i = 3; i <= n; i++) {
            result = one + two;
            one = two;
            two = result;
        }
        
        return result;
    }
};