Java memoization: minimum package count and cached subproblems

Java 8+. Use a JDK that supports this release.

Define a state before caching it

A shipping planner asks for the fewest packages that sum exactly to a target weight using allowed positive package sizes. The state is the remaining weight. A result of -1 means impossible; -2 means not computed.

For each usable size, solve the smaller remaining weight and keep the smallest successful count plus one. The zero-weight state returns zero packages. Positive sizes prove progress; a zero size would recurse into the same state forever.

The helper validates every size at the entry point. It also rejects negative targets. That keeps the recursive method focused on states already known to be valid.

The cache belongs to one input policy

Changing package sizes changes the meaning of every cached remaining-weight result. The sample creates a fresh cache for each call so results cannot leak across different policies.

This recursive implementation is useful for understanding repeated states, but large targets can exhaust the call stack. A bottom-up tabulation uses the same state relation without recursive frames.

The target value controls storage and work, not merely the number of digits needed to represent it. A large numeric input requires an admission limit even if parsing it is cheap.

Working program

import java.util.Arrays;

public class PackagePlanner {
    static int minimumPackages(int target, int[] sizes) {
        if (target < 0) throw new IllegalArgumentException("Negative target");
        for (int size : sizes) if (size <= 0) throw new IllegalArgumentException("Sizes must be positive");
        int[] cache = new int[Math.addExact(target, 1)];
        Arrays.fill(cache, -2); cache[0] = 0;
        return solve(target, sizes, cache);
    }
    static int solve(int remaining, int[] sizes, int[] cache) {
        if (cache[remaining] != -2) return cache[remaining];
        int best = Integer.MAX_VALUE;
        for (int size : sizes) {
            if (size > remaining) continue;
            int previous = solve(remaining - size, sizes, cache);
            if (previous >= 0) best = Math.min(best, previous + 1);
        }
        return cache[remaining] = best == Integer.MAX_VALUE ? -1 : best;
    }
    public static void main(String[] args) {
        System.out.println(minimumPackages(10, new int[]{3, 5}));
        System.out.println(minimumPackages(7, new int[]{3, 5}));
        System.out.println(minimumPackages(0, new int[]{3, 5}));
    }
}

Output

2
-1
0

Cost and design choices

For target W and K sizes, at most W + 1 states each inspect K sizes, giving O(WK) worst-case work. The cache uses O(W) integers. Recursive depth can also reach O(W) when size 1 is allowed.

A greedy choice of the largest fitting size is not correct for every package set. For sizes 1, 3, and 4 with target 6, two size-3 packages beat 4 plus two size-1 packages. A recurrence needs a proof; a plausible local choice is insufficient.

Common Mistakes

• Do not use the same sentinel for impossible and uncomputed.
• Do not admit zero or negative package sizes.
• Do not promise this scales to arbitrary target integers.

Connect the contracts

Caching a result does not repair missing base cases or recursive progress.

Compare cached calls with bottom-up state evaluation to account for traversal order and stack use.

Compare the boundary explained in Cache storage with the assumptions made by this program.