Pattern Recognition Drill
Easy Recursion
The Problem
Compute the nth Fibonacci number efficiently.
What approach would you use?
Think about it before scrolling down.
Memoize or tabulate. dp[i] = dp[i-1] + dp[i-2]. O(n) time, O(n) or O(1) space.
Naive recursion is O(2^n) — exponential. Adding @lru_cache makes it O(n).
Common Trap
The naive recursive tree is the textbook example of why memoization matters.