Memoization is the easiest way to turn a slow recursion into DP: keep the recursive function exactly as it is, and add a cache (the memo). Before solving a subproblem, look it up; if it's there, return the stored answer at once. Otherwise solve it, store the answer, and return it. Each distinct subproblem is now solved only once. It's called top-down because it starts from the question you want answered and recurses down only into the subproblems it actually needs.
n; for a grid it might be (row, col); for a knapsack (item, capacity).The first call to each fib(k) recurses and fills the memo; every later call is a lookup.
function fib(n, memo = new Map()) { if (n <= 1) return n; if (memo.has(n)) return memo.get(n); // computed before: reuse it const value = fib(n - 1, memo) + fib(n - 2, memo); memo.set(n, value); return value;}In Python, @functools.cache (or @lru_cache(None)) memoizes any function whose arguments are hashable — one line. In other languages, write the check and the store yourself.
Memoization still walks the call tree depth-first, but each state's subtree is explored only the first time; afterwards the state is a single lookup. So the walk really visits a DAG of states: fib(5) → fib(4) → fib(3) → fib(2) → fib(1), then returns upward, filling the memo from the smallest states first, exactly in the order their answers become available. You never decide the order yourself — the recursion finds it.
fib(5000) with @cache crashes with a RecursionError even though the work is tiny. Bottom-up tabulation (next lesson) has no stack at all.(i, remaining), caching on i alone returns wrong answers.def f(n, memo={}) keeps the same dict across calls; fine for fib, a bug when the inputs change.