Some problems break into smaller versions of themselves: the fewest batches to make 100 depends on the fewest to make 100 minus each batch size. Written as plain recursion, the same smaller questions are asked again and again, and the work explodes.
Dynamic programming answers each smaller question once and stores it, in an array indexed by the question. Then it either fills the table from the smallest questions up, or recurses and checks the table first ("memoisation"). In JavaScript, filling an array from the bottom avoids the call-stack limit that deep recursion hits.
The hard part is the state: what one entry of the table means. Write it as a sentence, such as "best[t] is the fewest batches that add up to exactly t", then write how an entry follows from smaller ones, then decide the starting entries. If the sentence is right, the code is short.
Greedy choices, such as always taking the largest batch, look like shortcuts but are often wrong. Dynamic programming considers every choice at each step, cheaply, because the rest of each choice is already in the table.
Recognise it
- The question asks for the fewest, most, longest or number of ways.
- A choice now leaves a smaller version of the same problem.
- A recursive solution would ask the same smaller question many times.
The shape of the code
const best = new Array(target + 1).fill(Infinity);
best[0] = 0; // the smallest question, answered directly
for (let t = 1; t <= target; t++) {
for (const choice of choices) {
if (choice <= t) best[t] = Math.min(best[t], best[t - choice] + 1);
}
}
return best[target] === Infinity ? -1 : best[target];