Lesson 167
Dynamic Programming
Memoization · Tabulation
1:00How to turn exponential brute-force recursion into linear-time solutions by storing subproblem answers — covering memoization, tabulation, space optimization, and the four-step DP recipe.
By the end, you can
- Explain what overlapping subproblems and optimal substructure mean, and why both are required for DP to apply.
- Trace the exponential call tree of naive Fibonacci and identify the duplicated subproblems.
- Implement a memoized (top-down) solution and explain the cache-check-then-store pattern.
- Build a bottom-up DP table iteratively, filling cells in dependency order.
- Apply the rolling-variable optimization to reduce O(n) space to O(1) when only the last two cells matter.
- Fill a 1-D DP table by hand for Fibonacci and climbing stairs, verifying each cell with the recurrence.
- Classify a DP problem as linear, grid, interval, or state machine and write the appropriate recurrence signature.
- Distinguish DP from greedy and divide-and-conquer, and choose the right paradigm for a given problem.
- Identify the three common DP pitfalls (bad base cases, wasted memory, wrong problem fit).
- Apply the four-step DP recipe (define state, recurrence, base cases, implement + optimize) to an unfamiliar problem.
Up next in Algorithms & Graph Algorithms
