How do you approach a dynamic programming problem?

A recipe that works for most interview DP problems:

1. Recognize it: the brute force is recursive and solves the same subproblems repeatedly (count paths, minimum cost, maximum value, number of ways).
2. State: the smallest description of a subproblem the rest depends on, like “the fewest coins for amount a” or “the edit distance between the first i and j characters”.
3. Transition: ask what the last decision was. “The last coin was c” gives fewest(a) = 1 + min over c of fewest(a − c).
4. Base cases: the trivially known states (amount 0, empty strings).
5. Order and answer: compute states after their dependencies; say which state is the answer.

Then implement it top-down (the recursion plus a shared memo, natural to write, visits only reachable states) or bottom-up (a table filled in order, no recursion depth issues, easy to space-optimize). Complexity is the number of states times the work per transition.

Say the trade-offs: rolling arrays reduce space (often O(n·m) to O(m)) but make reconstructing the actual choices harder; sentinels like Int.MAX_VALUE overflow when you add to them; and greedy is tempting but needs a proof, while DP doesn’t.