Dynamic programming is just recursion with a notebook

DP scared me until someone described it as "recursion that writes down answers so it never solves the same subproblem twice." Classic example: Fibonacci. Naive recursion recomputes fib(3) over and over, which is exponential. If you keep a table and check it before recursing, each value is computed once, which is linear. Two ways to write it: - Top-down (memoization): write the recursion, then add a cache. - Bottom-up (tabulation): fill the table from the smallest subproblems up. My checklist for any DP problem: What is a subproblem? What's the recurrence? What are the base cases? In what order do I fill the table?