Watch how memoization caches recursive Fibonacci calls, eliminating redundant computation and reducing complexity from O(2ⁿ) to O(n).
Memoization (Top-Down DP) caches the result of each sub-problem the first time it's solved. When the same sub-problem appears again, the answer is returned directly from the cache, with no recomputation.
Naive recursive fib(n) recomputes fib(2), fib(3)… exponentially many times. For fib(5), fib(3) is computed twice and fib(2) is computed three times. Time complexity: O(2ⁿ).
Store the result of fib(n) in a hash map after computing it. The next time fib(n) is called, return the stored value immediately (O(1) lookup). This reduces time to O(n).
Cyan = the call working right now, Amber = a value read out of the memo, Green = the final answer. Watch the right-hand call under fib(4) and every call above it: it is answered from the memo and never recurses.
DP requires two properties: (1) Overlapping sub-problems (same sub-problem solved multiple times) and (2) Optimal substructure (solution to big problem = combination of solutions to sub-problems). Fibonacci has both.
The memo cache eliminates exponential redundancy. Without it: O(2ⁿ). With it: O(n) time and O(n) space for the cache.