Dynamic programming
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
When it applies
Dynamic programming is for problems with overlapping subproblems and an optimal substructure: the best answer for a state is built from the best answers of smaller states. Always write the recursion first and only then decide between memoising it and filling a table bottom-up.
Signals: "fewest", "number of ways", "maximum value subject to", and any brute force whose recursion tree visibly repeats arguments.
The template
Write this from memory. Every problem in this section is a specialisation of it, and most bugs come from deviating without a reason.
best = [BASE] + [SENTINEL] * n
for state in range(1, n + 1):
for move in moves(state):
prev = state - move
if prev >= 0:
best[state] = min(best[state], best[prev] + cost(move))
return best[n]std::vector<int> best(n + 1, SENTINEL);
best[0] = BASE;
for (int state = 1; state <= n; ++state)
for (int move : moves(state))
if (state - move >= 0)
best[state] = std::min(best[state], best[state - move] + cost(move));
return best[n];int[] best = new int[n + 1];
java.util.Arrays.fill(best, SENTINEL);
best[0] = BASE;
for (int state = 1; state <= n; state++)
for (int move : moves(state))
if (state - move >= 0)
best[state] = Math.min(best[state], best[state - move] + cost(move));
return best[n];const best = new Array(n + 1).fill(SENTINEL);
best[0] = BASE;
for (let state = 1; state <= n; state++)
for (const move of moves(state))
if (state - move >= 0)
best[state] = Math.min(best[state], best[state - move] + cost(move));
return best[n];let mut best = vec![SENTINEL; n + 1];
best[0] = BASE;
for state in 1..=n {
for &mv in moves(state) {
if state >= mv {
best[state] = best[state].min(best[state - mv] + cost(mv));
}
}
}
best[n]-- A lazy array is the table; each entry may refer to earlier ones.
best = listArray (0, n) [f s | s <- [0 .. n]]
where f 0 = base
f s = minimum [best ! (s - m) + cost m | m <- moves s, m <= s]Problems
Largest sum with no two chosen positions adjacent
Two states, one recurrence, O(1) memory. The example to reach for when someone asks you to explain dynamic programming.
Open the problem → Medium20 minFewest coins to make an amount
Greedy fails, recursion repeats itself, and one array fixes both. The cleanest first dynamic programme.
Open the problem →Or sit a timed interview: a fixed window, limited submissions, and a report at the end.