Memoization vs Tabulation
Two ways to cache subproblem answers.
Why Cache at All
Naive recursion redoes the same work again and again. Dynamic programming stores each answer once so you never recompute it.
fib(40) # slow: recomputes endlesslyOverlapping Subproblems
DP applies when a problem splits into overlapping subproblems. The same smaller case shows up across many branches of the recursion.
fib(5) needs fib(3) twiceAll lessons in this course
- Memoization vs Tabulation
- Define State and Transition
- Climbing Stairs & Coin Combinations
- Longest Increasing Subsequence