Dynamic programming: minimum coins

A voucher service can issue credit in denominations 1, 3, and 4. An order needs exactly six units, and each voucher has the same handling cost, so the service wants the fewest vouchers. Largest first gives 4 + 1 + 1; two threes are better.

Trying every sequence finds the answer, but repeatedly solves the same remaining amounts. Dynamic programming gives each smaller amount one saved answer and builds the six-unit answer from those results.

Issuing an exact amount of credit

Minimum coins asks for an exact total with unlimited copies of each size. Greedily taking the largest size is not generally correct: sizes 1,3,4 with amount 6 lead greedy to 4+1+1, while 3+3 needs only two coins.

A recursive prototype explores every possible last coin without caching. The same remaining amounts reappear in many branches, making this a natural dynamic-programming problem.

Remembering the best smaller amounts

Define best[a] as the fewest coins forming amount a. best[0] is zero, and a positive amount can be reached by choosing a final coin c and extending best[a-c]. Process increasing amounts so all smaller dependencies are known. Keep an unreachable state distinct from a real zero-coin answer.

An amount+1 sentinel is sufficient for this exercise: any reachable total formed from positive integer sizes needs at most amount coins. Do not add to a sentinel representing unbounded infinity without considering its meaning. Duplicate sizes add repeated transitions but do not alter answers.

Validate all sizes even when amount is zero. A zero size creates a self-dependency; a negative size reverses the intended dependency order and can prevent recursion from terminating. Empty sizes produce zero for amount zero and impossibility for positive amounts.

const amount = 6;
const best = Array(amount + 1).fill(amount + 1);
best[0] = 0;
console.log(best[0], best[6]); // 0 7: base case and unreachable marker
console.log([3, 3].reduce((total, size) => total + size, 0)); // 6

When the amount is too large for a table

Uncached recursion can be exponential. Bottom-up DP costs O(amount * sizes.length) time and O(amount) storage, which depends on the numeric amount rather than its digit count. Use it when that table fits the workload. Greedy is only justified for denomination systems with a separate proof; a few passing examples do not establish that property.

The voucher service needs an exact total: an unreachable amount is different from a valid issue containing zero vouchers.