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

A locally largest coin may block an optimum: with 1,3,4, total 6 uses two 3s instead of 4,1,1. The subproblem asks for the minimum count for each exact smaller amount, and impossible states must stay distinct from zero coins.

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.

sizes, amount := []int{1, 3, 4}, 6
best := make([]int, amount+1)
for subtotal := 1; subtotal <= amount; subtotal++ {
	best[subtotal] = -1 // Unreachable until a valid predecessor is found.
	for _, size := range sizes {
		if size <= subtotal && best[subtotal-size] != -1 {
			candidate := best[subtotal-size] + 1
			if best[subtotal] == -1 || candidate < best[subtotal] {
				best[subtotal] = candidate
			}
		}
	}
}
fmt.Println(best[amount]) // 2: 3 + 3

When the amount is too large for a table

A dependency only points toward a smaller amount when all sizes are positive; zero or negative sizes break progress. Dynamic programming removes repeated exploration, trading amount-sized memory for polynomial work. This is pseudo-polynomial in the numeric amount, so huge integer amounts remain expensive. Greedy correctness needs additional denomination properties.

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.

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