Climbing Stairs

Climbing Stairs

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 climb to the top?

Solution

def climb_stairs(n):
    if n <= 2:
        return n
    
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

# Space optimized version
def climb_stairs_optimized(n):
    if n <= 2:
        return n
    
    prev, curr = 1, 2
    for i in range(3, n + 1):
        prev, curr = curr, prev + curr
    
    return curr

Analysis

Time Complexity: O(n)
Space Complexity: O(1) for optimized version

Approach

1. Dynamic Programming: Use DP to build solution from smaller subproblems
2. Fibonacci Pattern: Number of ways follows Fibonacci sequence
3. Space Optimization: Only need to keep track of previous two values

Edge Cases

• n = 0 (no steps)
• n = 1 (one step)
• n = 2 (two steps)
• Large values of n

Variations

• Min Cost Climbing Stairs: Each step has a cost
• Climbing Stairs with Constraints: Can’t climb certain steps
• Different Step Sizes: Can climb 1, 2, or 3 steps at a time