Climbing Stairs 20 XP Easy

LeetCode Ctrl+Enter Run Ctrl+S Save

You're climbing a staircase with n steps. Each time you can climb 1 or 2 steps. How many distinct ways can you reach the top?

# n=1: [1]                          → 1 way
# n=2: [1,1] or [2]                  → 2 ways
# n=3: [1,1,1] or [1,2] or [2,1]    → 3 ways
# n=4: 5 ways
# n=5: 8 ways
# Pattern: it's FIBONACCI! f(n) = f(n-1) + f(n-2)

Why Fibonacci? From step n, you could have gotten there from:

Step n-1 (taking 1 step) → there are f(n-1) ways to reach step n-1
Step n-2 (taking 2 steps) → there are f(n-2) ways to reach step n-2
Total: f(n) = f(n-1) + f(n-2)

This is a classic DP problem disguised as recursion. Use memoization or bottom-up iteration to avoid exponential time.

📋 Instructions

Implement `climb_stairs(n)` using recursion with memoization. Print results for n = 2, 3, 5, 10.

Base cases: n=1 → 1, n=2 → 2. Recursive: climb(n) = climb(n-1) + climb(n-2). Use a memo dict to cache results.

🧪 Test Cases

Input

climb_stairs(2)

Expected

2

Test case 1

Input

climb_stairs(3)

Expected

3

Test case 2

Input

climb_stairs(5)

Expected

8

Test case 3

Input

climb_stairs(10)

Expected

89

Test case 4

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›