Recursion to DP

You've just identified the problem: overlapping subproblems cause exponential slowdown. And the solution is dynamic programming (DP (dynamic programming))! I'll show you two approaches:

$1.$ memoization (top-down) adds a cache (a place to store results) to your recursive code, storing results as you compute them.

$2.$ Tabulation (bottom-up) builds an array iteratively (using a loop instead of recursion), filling it from base cases upward. Both give you $O(n)$ time instead of $O(2^n)$. Next, I'll walk you through both approaches and show you how to speed up your Fibonacci solution.