Climbing Stairs

Difficulty: Easy Source: NeetCode

Problem

You are climbing a staircase. It takes n steps to reach the top. Each time you can climb either 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1: Input: n = 2 Output: 2 (1+1, 2)

Example 2: Input: n = 3 Output: 3 (1+1+1, 1+2, 2+1)

Constraints:

• 1 <= n <= 45

Prerequisites

Before attempting this problem, you should be comfortable with:

• Recursion — breaking a problem into smaller subproblems
• Memoization — caching results to avoid repeated computation
• Dynamic Programming — building solutions bottom-up from base cases

1. Brute Force (Recursion)

Intuition

To reach step n, you had to come from either step n-1 (taking 1 step) or step n-2 (taking 2 steps). So the number of ways to reach n equals the ways to reach n-1 plus the ways to reach n-2. This is the Fibonacci recurrence. The brute force just recurses without caching, so it recomputes the same subproblems over and over.

Algorithm

1. Base cases: ways(0) = 1 (one way to stand at bottom), ways(1) = 1.
2. Recursive case: ways(n) = ways(n-1) + ways(n-2).

Solution

def climbStairs_brute(n):
    if n <= 1:
        return 1
    return climbStairs_brute(n - 1) + climbStairs_brute(n - 2)


print(climbStairs_brute(2))   # 2
print(climbStairs_brute(3))   # 3
print(climbStairs_brute(5))   # 8
print(climbStairs_brute(10))  # 89

Complexity

• Time: O(2^n) — each call branches into two more
• Space: O(n) — recursion stack depth

2. Dynamic Programming (Bottom-Up)

Intuition

Notice that ways(n) = ways(n-1) + ways(n-2) — this is just Fibonacci! Instead of recursing from the top, build up from the base cases. We only ever need the last two values, so we can use two variables instead of a full array. This is the cleanest and most efficient solution.

Algorithm

1. Handle base cases: if n == 1, return 1.
2. Initialize prev2 = 1 (ways to reach step 0) and prev1 = 1 (ways to reach step 1).
3. For each step from 2 to n: curr = prev1 + prev2, then slide the window.
4. Return curr.

Solution

def climbStairs(n):
    if n <= 1:
        return 1

    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr

    return prev1


print(climbStairs(1))   # 1
print(climbStairs(2))   # 2
print(climbStairs(3))   # 3
print(climbStairs(5))   # 8
print(climbStairs(10))  # 89
print(climbStairs(45))  # 1836311903

Complexity

• Time: O(n) — single pass
• Space: O(1) — only two variables

Common Pitfalls

Off-by-one in base cases. There is exactly 1 way to reach step 0 (do nothing) and 1 way to reach step 1 (take one step). Getting this wrong shifts all subsequent values.

Using a full DP array when only two values are needed. A common beginner pattern is dp = [0] * (n+1); dp[0] = dp[1] = 1. This works but uses O(n) space unnecessarily. Two variables are enough.

Mixing up Fibonacci indexing. Climbing stairs is Fibonacci starting at F(1)=1, F(2)=2, F(3)=3. Standard Fibonacci starts at F(0)=0, F(1)=1. Just make sure your base cases match the problem.