Dynamic programming.

// The state is the remaining postage amount. Dynamic programming works when that state is
// sufficient to describe the smaller problem and many paths ask for the same state again.
export function evaluate(problem: StampProblem, mode: Mode, trace = false): Evaluation {
	const { target, denominations } = validate(problem);
	const steps: Step[] = [];
	let calls = 0;
	let computed = 0;
	let transitions = 0;
	let peakFrames = 0;
	let minimum: number | null;
	let table: readonly (number | null)[] = [];

	if (mode === 'tabulated') {
		const result = tabulate(target, denominations);
		const traceTable = Array<number | null>(target + 1).fill(null);
		traceTable[0] = 0;
		for (let amount = 1; amount <= target; amount++) {
			const value = result.table[amount];
			traceTable[amount] = value;
			const stamp = result.choice[amount];
			transitions += denominations.filter((denomination) => denomination <= amount).length;
			if (trace) steps.push({ kind: 'fill', amount, value, stamp });
		}
		computed = target;
		table = traceTable;
		minimum = table[target] ?? null;
		return {
			mode,
			target,
			denominations,
			minimum,
			plan: planFromTable(target, result.choice, minimum),
			calls,
			computed,
			transitions,
			peakFrames,
			table,
			steps
		};
	}

	// The stamp that produced each amount's best answer, so the plan comes from this run.
	const choice = Array<number | null>(target + 1).fill(null);
	const memo = new Map<number, number>();
	if (mode === 'memoized') memo.set(0, 0);

	function solve(amount: number, depth: number): number {
		calls++;
		peakFrames = Math.max(peakFrames, depth + 1);
		const cached = mode === 'memoized' && memo.has(amount);
		if (trace) steps.push({ kind: 'call', amount, depth, cached });
		if (cached) {
			const value = memo.get(amount);
			if (value === undefined) throw new Error('missing memoized value');
			if (trace) steps.push({ kind: 'return', amount, depth, value: asResult(value) });
			return value;
		}
		computed++;
		if (amount === 0) {
			if (mode === 'memoized') memo.set(amount, 0);
			if (trace) steps.push({ kind: 'return', amount, depth, value: 0 });
			return 0;
		}
		if (amount < 0) {
			if (trace) steps.push({ kind: 'return', amount, depth, value: null });
			return IMPOSSIBLE;
		}

		let best = IMPOSSIBLE;
		for (const denomination of denominations) {
			if (denomination > amount) break;
			transitions++;
			const candidate = solve(amount - denomination, depth + 1) + 1;
			if (candidate < best) {
				best = candidate;
				choice[amount] = denomination;
			}
		}
		if (mode === 'memoized') memo.set(amount, best);
		if (trace) steps.push({ kind: 'return', amount, depth, value: asResult(best) });
		return best;
	}

	const rawMinimum = solve(target, 0);
	minimum = asResult(rawMinimum);
	if (mode === 'memoized') {
		const known = Array<number | null>(target + 1).fill(null);
		for (const [amount, value] of memo) {
			if (amount >= 0) known[amount] = asResult(value);
		}
		table = known;
	}
	return {
		mode,
		target,
		denominations,
		minimum,
		plan: planFromTable(target, choice, minimum),
		calls,
		computed,
		transitions,
		peakFrames,
		table,
		steps
	};
}

// The shortcut dynamic programming replaces: always take the largest stamp that still fits.
// For 6 cents with 1, 3, and 4 it takes 4 + 1 + 1, one stamp more than 3 + 3.
export function largestFirst(problem: StampProblem): { plan: number[]; count: number | null } {
	const { target, denominations } = validate(problem);
	const plan: number[] = [];
	let remaining = target;
	for (const stamp of [...denominations].reverse()) {
		while (stamp <= remaining) {
			plan.push(stamp);
			remaining -= stamp;
		}
	}
	return remaining === 0 ? { plan, count: plan.length } : { plan: [], count: null };
}

func Evaluate(problem Problem, mode Mode, trace bool) (Evaluation, error) {
	target, denominations, err := validate(problem)
	if err != nil {
		return Evaluation{}, err
	}
	if mode != Recursive && mode != Memoized && mode != Tabulated {
		return Evaluation{}, fmt.Errorf("unknown mode %q", mode)
	}
	evaluation := Evaluation{Mode: mode, Target: target, Denominations: denominations}
	if mode == Tabulated {
		table, reachable, choice, hasChoice := tabulate(target, denominations)
		evaluation.Table = table
		evaluation.TableReachable = reachable
		evaluation.Computed = target
		for amount := 1; amount <= target; amount++ {
			for _, stamp := range denominations {
				if stamp > amount {
					break
				}
				evaluation.Transitions++
			}
			if trace {
				step := Step{Kind: "fill", Amount: amount, Value: table[amount], Reachable: reachable[amount]}
				if hasChoice[amount] {
					step.Stamp = choice[amount]
					step.HasStamp = true
				}
				evaluation.Steps = append(evaluation.Steps, step)
			}
		}
		evaluation.Minimum = table[target]
		evaluation.Reachable = reachable[target]
		evaluation.Plan = planFromTable(target, choice, hasChoice, evaluation.Minimum, evaluation.Reachable)
		return evaluation, nil
	}

	const impossible = int(^uint(0) >> 1)
	// The stamp that produced each amount's best answer, so the plan comes from this run.
	choice := make([]int, target+1)
	hasChoice := make([]bool, target+1)
	memo := map[int]int{}
	if mode == Memoized {
		memo[0] = 0
	}
	var solve func(int, int) int
	solve = func(amount, depth int) int {
		evaluation.Calls++
		if depth+1 > evaluation.PeakFrames {
			evaluation.PeakFrames = depth + 1
		}
		_, cached := memo[amount]
		if mode != Memoized {
			cached = false
		}
		if trace {
			evaluation.Steps = append(evaluation.Steps, Step{Kind: "call", Amount: amount, Depth: depth, Cached: cached})
		}
		if cached {
			value := memo[amount]
			if trace {
				evaluation.Steps = append(evaluation.Steps, Step{Kind: "return", Amount: amount, Depth: depth, Value: value, Reachable: value != impossible})
			}
			return value
		}
		evaluation.Computed++
		if amount == 0 {
			if mode == Memoized {
				memo[amount] = 0
			}
			if trace {
				evaluation.Steps = append(evaluation.Steps, Step{Kind: "return", Amount: amount, Depth: depth, Value: 0, Reachable: true})
			}
			return 0
		}
		if amount < 0 {
			if trace {
				evaluation.Steps = append(evaluation.Steps, Step{Kind: "return", Amount: amount, Depth: depth, Value: impossible})
			}
			return impossible
		}
		best := impossible
		for _, denomination := range denominations {
			if denomination > amount {
				break
			}
			evaluation.Transitions++
			candidate := solve(amount-denomination, depth+1)
			if candidate != impossible && candidate+1 < best {
				best = candidate + 1
				choice[amount] = denomination
				hasChoice[amount] = true
			}
		}
		if mode == Memoized {
			memo[amount] = best
		}
		if trace {
			evaluation.Steps = append(evaluation.Steps, Step{Kind: "return", Amount: amount, Depth: depth, Value: best, Reachable: best != impossible})
		}
		return best
	}

	minimum := solve(target, 0)
	evaluation.Reachable = minimum != impossible
	if !evaluation.Reachable {
		// No exact plan: report zero with Reachable false, as tabulation does,
		// so the sentinel never reaches the public result.
		evaluation.Minimum = 0
		evaluation.Plan = []int{}
	} else {
		evaluation.Minimum = minimum
		evaluation.Plan = planFromTable(target, choice, hasChoice, minimum, true)
	}
	return evaluation, nil
}

// LargestFirst is the shortcut dynamic programming replaces: always take the largest stamp
// that still fits. For 6 cents with 1, 3, and 4 it takes 4 + 1 + 1, one stamp more than 3 + 3.
func LargestFirst(problem Problem) ([]int, bool, error) {
	target, denominations, err := validate(problem)
	if err != nil {
		return nil, false, err
	}
	plan := []int{}
	remaining := target
	for i := len(denominations) - 1; i >= 0; i-- {
		for denominations[i] <= remaining {
			plan = append(plan, denominations[i])
			remaining -= denominations[i]
		}
	}
	if remaining != 0 {
		return []int{}, false, nil
	}
	return plan, true, nil
}