Dynamic Programming — remembering to not re-compute

Recursion is elegant until it isn't. Naive Fibonacci recomputes fib(5) hundreds of times because the call tree branches without memory. DP is the discipline of noticing that repetition and paying for each unique subproblem exactly once.

Two properties must hold:

• Overlapping subproblems — the same smaller instance appears in many branches.
• Optimal substructure — the best answer to the whole is composed from best answers to parts.

If either is missing, DP is the wrong hammer.

Two styles, same idea

Memoization (top-down) keeps the recursive shape and adds a dict. Fastest path from "I see the recursion" to a working solution.

Tabulation (bottom-up) fills an array from the base case outward. Loses the pretty recursion but gains iteration speed, no stack limits, and often O(1) space via rolling variables.

Pick memoization while you're still discovering the recurrence. Convert to tabulation once the shape is clear.

The mental model shift

Stop asking "how do I compute f(n)?" Start asking "what are the states, and what's the transition?"

A state fully describes a subproblem — for Fib it's just n. For coin change it's amount. For edit distance it's (i, j). The transition is your recurrence.

Common pitfalls

• Mutable default arguments as caches leak across calls. Use functools.lru_cache or pass explicitly.
• Unhashable state (lists, sets) breaks memoization. Convert to tuples.
• Wrong iteration order in tabulation — you must compute dependencies before the cells that need them.

Try it

1. Add @functools.lru_cache(maxsize=None) above fib_naive and rerun with n=200.
2. Write grid_paths(m, n) counting paths from top-left to bottom-right of an m by n grid moving only right or down. State: (i, j). Transition: f(i,j) = f(i-1,j) + f(i,j-1).