Memoization vs Tabulation
Memoization (top-down): start with the recursive solution, cache results. Tabulation (bottom-up): fill a table starting from base cases and build toward the answer.
Memo = sticky notes on a fridge (top-down, write answers as you discover them). Tabulation = filling in a spreadsheet row by row (bottom-up, systematic). Both avoid re-cooking the same dish twice.
Memoization: natural to write, only computes needed subproblems, but has function call overhead and stack depth limits. Tabulation: iterative, O(1) extra space possible with rolling array, but requires explicit ordering of subproblems. Both have the same asymptotic complexity if all subproblems are needed. Space optimization: if dp[i] only depends on dp[i-1], keep only one or two rows instead of the full table.
Memoization with Python's @functools.lru_cache or @cache is clean but hits Python's recursion limit (default 1000) for deep problems — increase with sys.setrecursionlimit() or convert to tabulation. Tabulation ordering must respect dependencies — process subproblems before problems that depend on them. For 2D DP, this usually means iterating in increasing order of both dimensions. The 'pull' vs 'push' distinction: tabulation usually pulls from smaller subproblems, but push (from each state, update larger states) can be more natural for some problems.
I start with the recursive structure and memoize — it's faster to reason about correctness. Once I have the memoized solution working, I explain how to convert to tabulation by identifying the dependency order and filling the table bottom-up. For space optimization, I ask 'which previous states do I need?' — if only dp[i-1], I can use two variables instead of an array. In Python, I use @functools.cache for memoization to avoid writing the cache dictionary manually.
Memoization with Python's default recursion limit of 1000 will fail for inputs that produce recursion depth > 1000. Always mention this constraint and offer tabulation as the production-safe alternative. Also: if your memoization key doesn't capture all relevant state, you'll return incorrect cached results — the key must uniquely determine the subproblem.