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

Greedy denomination choice fails for sizes 1,3,4 and amount 6: choosing 4 first uses three coins, while 3+3 uses two. Minimum-coins DP asks which final coin completed each smaller amount. The answer for amount a depends on already solved amounts a-c.

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.

const Int amount = 6, unreachable = 7;
std::vector<Int> sizes{1, 3, 4}, best(amount + 1, unreachable);
best[0] = 0;
for (Int subtotal = 1; subtotal <= amount; ++subtotal) {
    for (Int size : sizes) {
        if (size <= subtotal && best[subtotal - size] != unreachable) {
            best[subtotal] = std::min(best[subtotal], best[subtotal - size] + 1);
        }
    }
}
std::cout << best[amount] << '\n'; // 2: 3 + 3

When the amount is too large for a table

Only extend reachable states; do not add one to an unbounded numeric infinity. Positive sizes ensure dependencies point to smaller amounts and recursion terminates. Zero size would create a self-dependency, so validation is not cosmetic. Duplicate sizes change work but not the answer. The recurrence computes O(amount*count) transitions and needs O(amount) memory. The uncached recursive prototype revisits overlapping subproblems and can be exponential; compare behavior on small inputs before considering performance.

For amount A and d denominations, the table uses O(A*d) time and O(A) storage. That is pseudo-polynomial: a short numeric input can request an enormous table. Positive denominations ensure every dependency points to a smaller amount. Counting combinations or limiting each denomination changes the recurrence.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

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