Climbing Stairs

Master this topic with zero to advance depth.

Climbing Stairs

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?

Visual Representation

n = 3
Ways:
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Total: 3 ways

Recursion Tree:
       (3)
      /   \
    (2)   (1)
   /   \    |
 (1)   (0) (0)

Easy

Examples

Input: n = 2
Output: 2
1 step + 1 step
2 steps

Input: n = 3
Output: 3
1 + 1 + 1
1 + 2
2 + 1

Approach 1

Level I: Brute Force (Recursion)

Intuition

To reach step n, you could have come from either step n-1 (by taking 1 step) or step n-2 (by taking 2 steps). Thus, the total ways $f(n) = f(n-1) + f(n-2)$ . This is exactly the Fibonacci sequence.

Thought Process

Base cases: If $n=0$ or $n=1$ , there is only 1 way.
Recursive step: Return $solve(n-1) + solve(n-2)$ .

Pattern Identification

This is Plain Recursion. The bottleneck is that it re-calculates the same steps many times, leading to an exponential time complexity.

⏱ O(2^n)💾 O(n) due to recursion stack

Detailed Dry Run

Call	n	Returns	Action
1	3	f(2) + f(1)	Recurse
2	2	f(1) + f(0)	Recurse
3	1	1	Base Case
4	0	1	Base Case

java

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

    public static void main(String[] args) {
        System.out.println("Ways to climb 3 stairs: " + climbStairs(3)); // 3
    }
}

Approach 2

Level II: Memoization (Top-Down)

Intuition

Cache the result of climb(n) using a memo table so each stair count is computed only once.

Visual

climb(5)
  climb(4) --cached after first call!
  climb(3) --cached after first call!
  ...
Only N unique calls made.

⏱ O(N)💾 O(N)

Detailed Dry Run

climb(4) = climb(3) + climb(2). climb(3) = climb(2) + climb(1). Both branches cache climb(2)=2.

java

import java.util.*;

public class Main {
    static Map<Integer, Integer> memo = new HashMap<>();
    public static int climbStairs(int n) {
        if (n <= 1) return 1;
        if (memo.containsKey(n)) return memo.get(n);
        int result = climbStairs(n - 1) + climbStairs(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(climbStairs(5)); // 8
    }
}

⚠️ Common Pitfalls & Tips

Python's lru_cache handles the caching automatically. In other languages, a HashMap or array of size N+1 is needed.

Approach 3

Level III: Optimal (DP + Space Optimization)

Intuition

Thought Process

Since we only need the last two results ( $f(n-1)$ and $f(n-2)$ ) to calculate the current one, we can use two variables instead of a full DP array. This is the Iterative approach with O(1) Space.

Logic Steps

Initialize prev1 = 1 (for step 1) and prev2 = 1 (for step 0).
Loop from 2 to n.
Calculate current = prev1 + prev2.
Update prev2 = prev1 and prev1 = current.

⏱ O(n)💾 O(1)

Detailed Dry Run

n = 3

i	current	prev1	prev2	Action
-	-	1	1	Init
2	1+1=2	2	1	Update variables
3	2+1=3	3	2	Update variables

java

public class Main {
    public static int climbStairs(int n) {
        if (n <= 1) return 1;
        int prev2 = 1; // n-2
        int prev1 = 1; // n-1
        for (int i = 2; i <= n; i++) {
            int current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }

    public static void main(String[] args) {
        System.out.println("Ways for 5 stairs: " + climbStairs(5)); // 8
    }
}

⚠️ Common Pitfalls & Tips

Be careful with base cases. If $n=0$ is considered 1 way (doing nothing), the logic holds. For $n=1$ , it's also 1 way. The loop should start from 2.

← Previous QuestionPartition Equal Subset Sum

Next Question →Regular Expression Matching

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.