Course4all

Climbing Stairs

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Dynamic Programming.

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. 1 step + 1 step
  2. 2 steps
Input: n = 3
Output: 3
  1. 1 + 1 + 1
  2. 1 + 2
  3. 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)f(n) = f(n-1) + f(n-2). This is exactly the Fibonacci sequence.

Thought Process

  1. Base cases: If n=0n=0 or n=1n=1, there is only 1 way.
  2. Recursive step: Return solve(n−1)+solve(n−2)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

CallnReturnsAction
13f(2) + f(1)Recurse
22f(1) + f(0)Recurse
311Base Case
401Base 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)f(n-1) and f(n−2)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

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

Detailed Dry Run

n = 3
icurrentprev1prev2Action
--11Init
21+1=221Update variables
32+1=332Update 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=0n=0 is considered 1 way (doing nothing), the logic holds. For n=1n=1, it's also 1 way. The loop should start from 2.

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionPartition Equal Subset Sum
Next Question →Regular Expression Matching