Java minimum coin change: reachable states and impossible totals

The complete program targets Java 8. Compile it as one source file; its output is checked against the lesson.

An unreachable state is not zero

A voucher issuer supports denominations three and five. It must find the minimum voucher count for an exact total, or report that no combination exists. Initializing every state to zero would make nonexistent predecessor states look like free money.

The recurrence starts at zero vouchers for total zero and marks other totals unreachable. For each total it considers every denomination that fits. The resulting state represents exact totals with unlimited reuse of the supplied positive denominations.

Input bounds are part of the algorithm

A denomination of zero creates a self-dependency and a negative one violates the recurrence. Reject both. The target is capped at one million to bound allocation and prevent target-plus-one overflow in this implementation.

This is not a greedy algorithm. Choosing the largest denomination first can miss a better combination or fail when a smaller-first combination exists. A bounded supply of each denomination is another problem and needs a count-sensitive state transition.

Working program

import java.util.Arrays;
public class VoucherMinimum {
    static int minimum(int[] denominations, int target) {
        if (target < 0 || target > 1000000 || denominations.length == 0) throw new IllegalArgumentException("target or coins");
        for (int coin : denominations) if (coin <= 0) throw new IllegalArgumentException("coin");
        int missing = target + 1;
        int[] best = new int[target + 1]; Arrays.fill(best, missing); best[0] = 0;
        for (int amount = 1; amount <= target; amount++) {
            for (int coin : denominations) if (coin <= amount && best[amount - coin] != missing)
                best[amount] = Math.min(best[amount], best[amount - coin] + 1);
        }
        return best[target] == missing ? -1 : best[target];
    }
    public static void main(String[] args) {
        System.out.println(minimum(new int[]{3, 5}, 11));
        System.out.println(minimum(new int[]{3, 5}, 4));
        System.out.println(minimum(new int[]{3, 5}, 0));
        try { minimum(new int[]{0, 5}, 9); } catch (IllegalArgumentException rejected) { System.out.println("coin rejected"); }
    }
}

Output

3
-1
0
coin rejected

Costs and boundaries

For target t and k denominations the running time is O(tk) and state storage is O(t). Duplicate denominations repeat work without changing the optimum. The code returns the count only; reconstructing an actual voucher list needs predecessor information.

Common Mistakes

• Do not initialize unreachable amounts as zero.
• Reject non-positive denominations.
• Unlimited reuse and bounded inventory need different transitions.

Read next

Java bottom-up tabulation: dependency order and unreachable states, Java 0/1 knapsack: reverse capacity iteration prevents reuse, Java greedy interval selection: an exchange proof and a limited objective.

Compare the Python boundary

Python memoization: cache bounded states without hiding recursion depth.