Dynamic programming foundations

Why it matters

Dynamic programming turns exponential search into polynomial time whenever the same subproblems recur. In interviews it matters as much for what it reveals as for the problems themselves: can you define what a subproblem means, argue that a recurrence covers every case, and avoid the initialization and off-by-one bugs that DP code invites? Outside interviews the pattern appears in edit distance and sequence alignment, Viterbi decoding, join-order selection in query optimizers and resource allocation, anywhere results of subcomputations can be reused.

Core ideas

MIT 6.006 frames DP design as a checklist (SRTBOT) that is worth saying aloud:

• Subproblems: a precise definition, such as "best[i] is the maximum total from the first i houses". Most DP bugs trace back to a vague state.
• Relate: compute a subproblem from smaller ones by case analysis on one decision: either house i-1 is robbed or it is not, so best[i] = max(best[i-1], best[i-2] + value[i-1]).
• Topological order: an order in which dependencies are ready, here increasing i. If none exists, the recurrence has a cycle and is not well founded.
• Base cases: best[0] = 0 and best[1] = value[0].
• Original problem: best[n].
• Time: number of states times work per state, here O(n).

A relation is complete when the cases for the decision are exhaustive, and for counting they must also be disjoint. Counting ordered sequences when the problem wants unordered combinations is a typical failure of that test.

Top-down versus bottom-up. Memoization wraps the brute-force recursion with a cache: it is easy to derive and evaluates only reachable states, but its recursion depth equals the longest dependency chain, and deep chains exceed Python's default recursion limit of 1000 frames. Tabulation fills an array in a topological order: no recursion and easy space optimization, but you must find the order and you compute every state. Asymptotic time is the same.

from functools import cache

def min_coins(coins, amount):
    @cache
    def f(a):                      # fewest coins summing to exactly a
        if a == 0:
            return 0
        best = float('inf')
        for c in coins:
            if c <= a:
                best = min(best, f(a - c) + 1)
        return best
    result = f(amount)
    return -1 if result == float('inf') else result

The bottom-up version is a loop over a from 1 to amount; it avoids the depth problem when amount is large.

DP as a DAG. States are vertices and transitions are edges; the answer is a shortest, longest or counted path. This view explains why a valid evaluation order is a topological order and why the running time is proportional to the number of transitions.

Reconstruction. Store which choice achieved each optimum, or recompute it by checking which transition matches the stored value, then walk back from the original problem. Interviewers often ask for the items, not just the number.

Space optimization. If state i depends only on i-1 and i-2, keep two variables. Do this after the full version is correct, because reconstruction usually needs the full table or a parent array.

Identity values. Counting uses 0 for impossible and 1 for the empty way; minimization uses infinity for impossible; feasibility uses booleans. Mixing them up causes wrong answers on edge cases such as an amount of 0.

Common misconceptions

• "DP means filling a table." The table is an implementation detail; the state definition and recurrence are the solution. Say them before coding.
• "Memoization is slower than tabulation." They match asymptotically; memoization pays call overhead and recursion depth, tabulation computes states that may be unreachable. Choose by clarity and constraints.
• "Adding a cache to any recursion makes it efficient." Only if the number of distinct states is small; caching on a huge or unbounded state, such as a whole remaining list, does not help.
• "If greedy fails, the problem is hopeless." It usually means choices interact, which is exactly where a DP over the right state works.
• "Space optimization is always safe." It discards what reconstruction needs, and with the wrong loop order it reads values that were already overwritten.

How to approach it

Start from a correct brute-force recursion that makes one decision per call; its parameters become the state. Count states and work per state to get the complexity before adding the cache. Then choose top-down or bottom-up, write base cases first, and hand-run the smallest non-trivial input. Interviewers at every level expect a clearly stated state and recurrence; stronger candidates explain why the cases are exhaustive, reconstruct the solution, and optimize space only after correctness is established.