Easy
Climbing Stairs
👶 The 5-Year-Old Summary
You can take 1 or 2 steps at a time. How many ways to reach the top of 5 stairs? To reach step 5, you came from step 4 (taking 1) OR step 3 (taking 2)!
🎮 Interactive Visualizer
n = 5 stairs
🧠The Brain Hack
Fibonacci pattern! ways(n) = ways(n-1) + ways(n-2). It's exactly the Fibonacci sequence! Just remember: step 1 = 1 way, step 2 = 2 ways!
💻 The Clean Solution
def climb_stairs(n):
# Base cases
if n <= 2:
return n
# Build up from bottom
prev2, prev1 = 1, 2
for i in range(3, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1
# n=1: 1 way (1)
// n=2: 2 ways (1+1, 2)
// n=3: 3 ways (1+1+1, 1+2, 2+1)
// n=5: 8 ways!Time: O(n)
Space: O(1)