Sign in to watch this lesson
Algorithms - Dynamic Programming · 5:23
What DP Is: Memoization vs Tabulation
Dynamic programming means never redoing work: the naive Fibonacci tree for f(29) makes 1,664,079 calls, while the same recursion with a memo pad makes 57 (about 29,000 times fewer). We collapse the call tree into a thin DAG (top-down memoization), flip it into a loop over an array (bottom-up tabulation), shrink the array to a 3-slot ring buffer, and watch f(47) overflow a 32-bit int. Then the recipe every later DP lesson follows (state, transition, base cases, order, answer, memory), the cost of array vs hash-map tables measured on this Mac, and the die-reroll interview question solved by backward induction, the Bellman equation in miniature.
You will learn
- Explain why naive recursion on overlapping subproblems is exponential, and count the calls a memo saves (f(29): 1,664,079 vs 57).
- Write the same DP top-down (recursion plus a memo with a sentinel such as -1) and bottom-up (a loop from the base cases), and choose between them by state sparsity, recursion depth and memory.
- Apply the recipe state, transition, base cases, order, answer, memory, and estimate running time as number of states times work per state, including the cost of the table (array vs unordered_map vs map).
- Solve a small optimal-stopping problem by backward induction and recognise it as a Bellman equation on a DAG of states.