Climbing Stairs (DP) 15 XP Easy

LeetCode Ctrl+Enter Run Ctrl+S Save

This is LeetCode #70: Climbing Stairs — the perfect first DP problem! It's literally Fibonacci in disguise. 🪜

💡 Think of it like this: You're climbing a staircase with n steps. Each time you can take 1 step or 2 steps. How many different ways can you reach the top?

# For n=4 steps, here are ALL the ways:
# 1+1+1+1  = 4 steps (one at a time)
# 1+1+2    = 4 steps  
# 1+2+1    = 4 steps
# 2+1+1    = 4 steps
# 2+2      = 4 steps
# Total: 5 ways

The DP Insight: To reach step n, you came from either step n-1 (took 1 step) or step n-2 (took 2 steps). So:

ways(n) = ways(n-1) + ways(n-2) — That's Fibonacci!

Step 1: 1 way (just take 1 step)
Step 2: 2 ways (1+1 or 2)
Step 3: 3 ways (1+1+1, 1+2, 2+1)
Step 4: 5 ways (= 3 + 2)
Step 5: 8 ways (= 5 + 3)

💭 Your turn! Take what you learned above and write the code yourself. Struggling is part of learning! 🧠

This is the simplest form of DP. Master this pattern and you'll handle House Robber, Coin Change, and many more DP problems!

📋 Instructions

Find number of ways to climb n stairs. Print for n=5.

Same as Fibonacci with base cases dp[0]=1, dp[1]=1. You've got this — take it step by step!

⚠️ Try solving it yourself first — you'll learn more!

def climbStairs(n):
    if n <= 2:
        return n
    a, b = 1, 2    # dp[1]=1, dp[2]=2
    for i in range(3, n + 1):
        a, b = b, a + b  # dp[i] = dp[i-1] + dp[i-2]
    return b

# Only 2 variables needed! O(n) time, O(1) space

🧪 Test Cases

Input

climbStairs(5)

Expected

8

Test case 1

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›