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

Find the fewest unlimited positive sizes that sum exactly to a target. A locally large denomination can leave a remainder requiring more pieces or make an otherwise reachable target appear impossible.

Greedy choice is not correct for arbitrary sizes, while uncached recursion recomputes the same remainder repeatedly. Dynamic programming names each exact smaller amount and distinguishes unreachable from a reachable cost of zero.

Remembering the best smaller amounts

Let best[x] be the fewest vouchers making exactly x, with best[0] = 0. For six units, consider the final voucher: a 1 follows best[5], a 3 follows best[3], and a 4 follows best[2]. Add one to each reachable predecessor and take the minimum. An unreachable amount needs its own marker; zero already means a valid empty issue.

Greedy choices fail for sizes 1,3,4 and amount 6: choosing 4 needs three units while 3+3 needs two. A DP state records the best count for an exact smaller amount, with an unreachable sentinel that cannot be mistaken for zero. Final O(amount*numberOfSizes) time and O(amount) space.

The recurrence needs an explicit unreachable value that cannot masquerade as a free solution:

import java.util.*;

class Example {
    public static void main(String[] args) {
        int amount = 6;
        int unreachable = amount + 1;
        int[] best = new int[amount + 1];
        Arrays.fill(best, unreachable);
        best[0] = 0;
        assert best[0] == 0;
        assert best[3] == unreachable;
    }
}

The zero state means no pieces are needed to make zero; the other initialized states mean not yet reachable. A complete DP still has to consider every eligible size and convert the final sentinel to -1. Nonpositive sizes would destroy the smaller-state dependency.

When the amount is too large for a table

Exact-amount dynamic programming appears in change-making, bounded-size packaging variants, and combinational resource planning. Its cost depends on the numeric target, so O(amount) memory is pseudo-polynomial rather than a claim about input bit length.

Sizes are unlimited positive integers. Return minimum count summing exactly to amount or -1 when impossible. Zero amount returns zero, even for empty sizes. Reject negative amount and all nonpositive sizes before computing.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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