Dynamic Programming: Overlapping Subproblems

in reviewThis lesson is complete and being validated before release - details may still change.

Dynamic programming

Loading interactive demo…

The tree is the recursion: each node asks for the fewest coins that make its amount, and its children are the amounts each coin leaves. The grid at the side has one row per amount and one column per coin, each cell a try. The strips beneath are the table of answers by amount, the coins, the verdict, and the tapped amount. In table mode there is no tree: the grid and the table are the whole picture.Take the tour, or press and explore. Legend:

The panel beside the stage is the real CoinChange class from the published library executing in your browser, with the current line highlighted.

The call or table entry this step concerns, and the tapped amount.
A call still waiting on its coins, and a coin being tried.
A base case: zero needs no coins. On the grid, the coin that won an amount.
A memo hit: an amount answered from the table instead of recursing.
A call that has returned its answer, and a try whose coin fits.
A coin too large for its amount, and an amount no coins can make.
The faint finished tree and grid, before play reaches them.

calls counts the asks so far, memo hits the asks answered from the table, subproblems the distinct amounts solved; best is the target's answer once it is known and coins the combination that reaches it.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

A problem made of smaller copies of itself. What is the fewest number of coins that make an amount $A$ from denominations $c_1, \dots, c_k$ ? Whatever the answer is, it starts with some coin $c_i$ , and the rest of it must be the fewest coins for $A - c_i$ . So the answer is defined by its own smaller copies:

f(0) = 0, \qquad f(A) = 1 + \min_{c_i \le A} f(A - c_i)

with $f(A) = \infty$ when no coin fits with a makeable remainder. That recurrence is the whole algorithm; the three modes on the stage are three ways of running it.

Why the naive tree explodes. Written as plain recursion, $f(A)$ calls $f(A - c_i)$ for each coin, and each of those calls fans out again, so the tree has about $k^{A/\bar c}$ nodes: exponential in the amount. On the stage the tree for coins 1, 3, 4 at amount 6 has 24 nodes, and every step of the amount slider roughly doubles it. Look at the amounts on the nodes: 2 appears several times, each with its own subtree, worked out from scratch. Those repeats are the overlapping subproblems. There are only $A$ distinct amounts, yet the tree asks about them exponentially often.

Memoization: solve each amount once. Keep a table indexed by amount. When a call returns, store its answer; when a call starts, look first. The second ask for any amount is a hit: one lookup in place of a whole subtree. Every amount is now solved at most once, and each solution tries $k$ coins, so the work is

O(A \cdot k)

in time and $O(A)$ in space, down from exponential. Nothing about the recurrence changed; only the repeated work was removed. This top-down form is what memoized on the stage runs: the tree still appears, but every repeated amount collapses to a hit.

Bottom up: drop the recursion. Since $f(A)$ depends only on smaller amounts, fill the table from $f(1)$ upward; by the time the loop reaches $A$ , every $f(A - c_i)$ is already there. Same table, same $O(A \cdot k)$ , no call stack. This is the table mode: the tree is gone and the grid fills one row at a time. Top-down solves only the amounts the target actually needs and is easy to write from the recurrence; bottom-up has no recursion depth to worry about and a loop order that a compiler and a cache both like.

Reading the answer back. A count alone is not a plan. Each table entry also keeps the coin that won it, so from $A$ you take that coin, move to $A - c$ , and repeat until zero: the coins readout. Reconstruction is a walk down the table, $O(A)$ , and it is the reason the store records a coin and not just a number.

The two properties. Dynamic programming applies when a problem has optimal substructure, meaning an optimal answer is built from optimal answers to subproblems, which is what lets the recurrence take a $\min$ over them, and overlapping subproblems, meaning the same subproblems recur, which is what makes the table pay. Merge sort has the first property but not the second: its halves never repeat, so it is divide and conquer, and a memo would store each entry once and never read it.

Why not greedy. Taking the largest coin that fits is tempting and sometimes right: for 1, 2, 5 it always is. For 1, 3, 4 at amount 6 greedy takes a 4 and then two 1s, three coins, while the table finds 3 + 3. Greedy commits to the first coin without knowing what it costs later; the recurrence tries every first coin and lets the stored answers below decide. Left out here on purpose: the related question of how many ways to make an amount, the unbounded versus bounded variants, and reconstructing when several coins tie.

Where this goes next. The Core Data Structures arc closes here. The same recipe, a recurrence over smaller copies plus a table, gives the roadmap's edit distance lesson, where the subproblems are pairs of prefixes and the table is two-dimensional, and the knapsack lesson, where each item is a decision and the table runs over remaining capacity.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

One recurrence, three drivers. recurse is the recurrence written as it reads, and tabulate is the same loop body inside a for over amounts. The mode only decides whether recurse consults solved before fanning out, so naive and memoized differ by one lookup.
solved is the table. A Map from amount to best, filled on the way back up in the recursive modes and from 1 upward in table mode. choice beside it records the coin that won, which is all reconstruct needs to spell the answer out.
A sentinel, not infinity. An amount nothing makes is COIN_IMPOSSIBLE, a plain integer, so every value in the trace is an integer the stage can render and compare without floating-point surprises; rest + 1 < best is guarded by a check for the sentinel first.
Every try is traced, even a miss. A coin larger than the amount emits try with fits: false and is skipped. The grid draws those as dead cells, so the picture shows where the recurrence chose not to recurse, not only where it did.
id and parent build the tree. Each call numbers itself and names its caller, so the stage can lay out the recursion as a tree without replaying it. In table mode the ids are -1: there is no tree, and the stage draws none.
The naive mode stores too. It fills solved on the way back so subproblems can count distinct amounts, but it never reads the map; that one unread write is the difference between exponential and linear.

Richard Bellman worked out dynamic programming at the RAND Corporation in the early 1950s to plan decisions that come in stages, where the best choice now depends on the best choices later. His principle of optimality says that whatever the first step, the rest of an optimal plan must itself be optimal, which is what lets an answer be built from stored answers to smaller problems. His 1957 book collected the method; memoization, the computing habit of remembering a function's results, was named a decade later, and the two met in the recipe every algorithms course teaches.

1950Richard Bellman - Spends the fall quarter at RAND, where his first task, by his own account, is finding a name for the mathematics of multistage decision processes.source
1952Richard Bellman - His first paper using the term dynamic programming appears, a year before the Secretary of Defense his naming story blames for the word choice took office.source
1957Richard Bellman - Publishes the book Dynamic Programming, setting out the Bellman equation: the value of a state is the best over its choices of the immediate cost plus the value of what follows.source
1968Donald Michie - 'Memo Functions and Machine Learning' in Nature describes functions that remember their results, from the Latin memorandum; memoization is the top-down half of dynamic programming.source
1975J. W. Wright - The classic bottom-up dynamic programming solution to change-making, filling every amount from the smallest up in O(nW) time for n coin kinds and amount W.source

Used today

Shortest paths - Dijkstra's rule that a shortest path is made of shortest paths is Bellman's principle of optimality; Bellman-Ford relaxes every edge over a table of distances.
Comparing sequences - Edit distance, diff tools, and the Needleman-Wunsch and Smith-Waterman alignments of DNA all fill a table of prefix pairs, each cell from three neighbors.
Packing and planning - The knapsack problem, scheduling, and resource allocation share the shape: a decision now, and the best answer for what remains.

Did you know

Bellman wrote that he chose the word dynamic because it was something not even a Congressman could object to, and programming to avoid the word research, which the Secretary of Defense disliked; his first paper using the name predates that Secretary's term, so the story is disputed.source
Harold Kushner reported Bellman saying he was trying to upstage Dantzig's linear programming by adding the word dynamic.source
Memoization is not a misspelling of memorization: it comes from memorandum, something to be remembered, and names a function that keeps a memo of the answers it has already given.source
India once had coins of 5, 10, 20, and 25 paise, and 40 paise shows why greedy change fails: the largest coin first gives 25 + 10 + 5, three coins, where two 20s would do.source
Bellman published 619 papers and 39 books, more than 100 of the papers in the last eleven years of his life after brain surgery left him severely disabled.source

mode

coins

amount6

calls: 14
memo hits: 5
subproblems: 6 of 6
best: 2 coins
coins: 3 + 3

coin-change.ts

import type { Tracer } from "../trace";/** How the solver reaches the subproblems: plain recursion, recursion with a memo, or a table filled from the bottom. */export const COIN_MODES = ["naive", "memo", "table"] as const;export type CoinMode = (typeof COIN_MODES)[number];/** The answer for an amount no combination of the coins can make. */export const COIN_IMPOSSIBLE = -1;/** The largest amount a solver takes, so a naive recursion stays traceable. */export const COIN_MAX_AMOUNT = 12;/** The most denominations one solver takes. */export const COIN_MAX_KINDS = 4;/** The largest denomination. */export const COIN_MAX_VALUE = 20;export interface CoinChangeOptions {  /** Default memo. */  mode?: CoinMode;}export interface CoinChangeReport {  amount: number;  /** The fewest coins that make the amount, or COIN_IMPOSSIBLE. */  best: number;  fewestCoins: number;  /** One combination that reaches best, largest coin first; empty when impossible or zero. */  coins: number[];  /** Recursive calls made (none in table mode). */  calls: number;  /** Calls answered from the memo. */  hits: number;  /** Distinct amounts whose answer was worked out, the base case not counted. */  subproblems: number;}/** * The fewest coins that make an amount: the smallest problem that shows * what dynamic programming is. The answer for an amount is one coin * plus the best answer for what remains after that coin, over every * coin that fits, so the problem is defined by its own smaller copies. * Written as plain recursion that definition is exponential, because * the same remainders come up again and again down different branches * of the call tree: the overlapping subproblems. Remembering each * answer the first time (a memo) turns the tree into a table of amounts * with one entry each, and filling that table from zero upward (bottom * up) needs no recursion at all. The coin that won each amount is kept, * so the actual coins can be read back from the table. * * Time: O(k^amount) naive, O(amount * k) memoized or tabulated, with k * denominations. Space: O(amount) for the table and the recursion. */export class CoinChange {  readonly mode: CoinMode;  readonly coins: readonly number[];  /** The best answer for each amount worked out so far. */  private readonly solved = new Map<number, number>();  private readonly answersSoFar = new Map<number, number>();  /** The coin that reached each amount's best answer. */  private readonly choice = new Map<number, number>();  private calls = 0;  private hits = 0;  private nextId = 0;  constructor(coins: readonly number[], options: CoinChangeOptions = {}, private readonly tracer?: Tracer) {    if (coins.length === 0 || coins.length > COIN_MAX_KINDS) throw new RangeError(`coins must hold 1 to ${COIN_MAX_KINDS} denominations`);    for (const coin of coins) {      if (!Number.isInteger(coin) || coin < 1 || coin > COIN_MAX_VALUE) throw new RangeError(`coin ${coin} must be a whole number in [1, ${COIN_MAX_VALUE}]`);    }    if (new Set(coins).size !== coins.length) throw new RangeError("coins must be distinct");    this.coins = [...coins].sort((a, b) => a - b);    this.mode = options.mode ?? "memo";  }  /** Solves one amount from scratch and reports the answer with the work it took. */  solve(amount: number): CoinChangeReport {    if (!Number.isInteger(amount) || amount < 0 || amount > COIN_MAX_AMOUNT) throw new RangeError(`amount must be a whole number in [0, ${COIN_MAX_AMOUNT}]`);    this.solved.clear();    this.answersSoFar.clear();    this.choice.clear();    this.calls = 0;    this.hits = 0;    this.nextId = 0;    const best = this.mode === "table" ? this.tabulate(amount) : this.recurse(amount, -1, 0);    const fewestCoins = this.mode === "table" ? this.tabulate(amount) : this.recurse(amount, -1, 0);    return { amount, best, coins: this.reconstruct(amount, best), calls: this.calls, hits: this.hits, subproblems: this.solved.size };    return { amount, fewestCoins, coins: this.reconstruct(amount, fewestCoins), calls: this.calls, hits: this.hits, subproblems: this.answersSoFar.size };  }  /** Top down: the answer for an amount from the answers for the amounts each coin leaves. */  private recurse(amount: number, parent: number, depth: number): number {    const id = this.nextId++;    this.calls++;    // ▸ ask for the fewest coins that make this amount; one call per ask    this.tracer?.emit("call", { id, parent, depth, amount });    if (amount === 0) return this.base(id);    const remembered = this.mode === "memo" ? this.solved.get(amount) : undefined;    const remembered = this.mode === "memo" ? this.answersSoFar.get(amount) : undefined;    if (remembered !== undefined) {      this.hits++;      // ▸ this amount was answered before, so reuse the stored answer instead of recursing      this.tracer?.emit("hit", { id, amount, best: remembered });      this.tracer?.emit("hit", { id, amount, fewestCoins: remembered });      return remembered;    }    const { best, chosen } = this.choose(id, amount, (sub) => this.recurse(sub, id, depth + 1));    const { fewestCoins, chosen } = this.choose(id, amount, (remainder) => this.recurse(remainder, id, depth + 1));    this.choice.set(amount, chosen);    this.solved.set(amount, best);    this.answersSoFar.set(amount, fewestCoins);    if (this.mode === "memo") this.store(amount, best, chosen);    if (this.mode === "memo") this.store(amount, fewestCoins, chosen);    // ▸ the best over the coins that fit goes back up to whoever asked    this.tracer?.emit("return", { id, amount, best, coin: chosen });    this.tracer?.emit("return", { id, amount, fewestCoins, coin: chosen });    return best;    return fewestCoins;  }  /** Bottom up: every amount from 1 to the target, each from the entries already filled beneath it. */  private tabulate(amount: number): number {    this.base(-1);    for (let target = 1; target <= amount; target++) {      const { best, chosen } = this.choose(-1, target, (sub) => (sub === 0 ? 0 : this.solved.get(sub)!));      const { fewestCoins, chosen } = this.choose(-1, target, (remainder) => (remainder === 0 ? 0 : this.answersSoFar.get(remainder)!));      this.solved.set(target, best);      this.answersSoFar.set(target, fewestCoins);      this.choice.set(target, chosen);      this.store(target, best, chosen);      this.store(target, fewestCoins, chosen);    }    return amount === 0 ? 0 : this.solved.get(amount)!;    return amount === 0 ? 0 : this.answersSoFar.get(amount)!;  }  /** Amount zero needs no coins: the one base case, whether a call reached it or the table starts from it. */  private base(id: number): number {    // ▸ zero needs no coins: the bottom of every branch    this.tracer?.emit("base", { id, amount: 0 });    return 0;  }  /** The recurrence itself: one coin plus the best answer for what it leaves, over every coin that fits; `rest` says how a remainder's answer is reached. */  private choose(id: number, amount: number, rest: (sub: number) => number): { best: number; chosen: number } {  private choose(id: number, amount: number, rest: (remainder: number) => number): { fewestCoins: number; chosen: number } {    let best = COIN_IMPOSSIBLE;    let fewestCoins = COIN_IMPOSSIBLE;    let chosen = 0;    for (const coin of this.coins) {      const sub = amount - coin;      const remainder = amount - coin;      const fits = sub >= 0;      const fits = remainder >= 0;      // ▸ for each coin, what it leaves must be made with one coin fewer      this.tracer?.emit("try", { id, amount, coin, sub, fits });      this.tracer?.emit("try", { id, amount, coin, remainder, fits });      if (!fits) continue;      const answer = rest(sub);      const answer = rest(remainder);      if (answer === COIN_IMPOSSIBLE) continue;      if (best === COIN_IMPOSSIBLE || answer + 1 < best) {      if (fewestCoins === COIN_IMPOSSIBLE || answer + 1 < fewestCoins) {        best = answer + 1;        fewestCoins = answer + 1;        chosen = coin;      }    }    return { best, chosen };    return { fewestCoins, chosen };  }  /** An answer written down for good: the memo's entry or the table's cell. */  private store(amount: number, best: number, chosen: number): void {  private store(amount: number, fewestCoins: number, chosen: number): void {    // ▸ remember the answer for this amount, so it is worked out only once    this.tracer?.emit("store", { amount, best, coin: chosen });    this.tracer?.emit("store", { amount, fewestCoins, coin: chosen });  }  /** Reads the coins back from the choices, largest first. */  private reconstruct(amount: number, best: number): number[] {  private reconstruct(amount: number, fewestCoins: number): number[] {    if (best === COIN_IMPOSSIBLE) return [];    if (fewestCoins === COIN_IMPOSSIBLE) return [];    const coins: number[] = [];    let left = amount;    while (left > 0) {      const coin = this.choice.get(left);      if (coin === undefined || coin === 0) break;      coins.push(coin);      left -= coin;    }    return coins.sort((a, b) => b - a);  }}

amount =: 6
best =: 2 coins
coins =: 3 + 3
calls =: 14
hits =: 5
subproblems =: 6

Done in memoized mode: 6 takes 2 coins, 3 + 3, after 14 calls, 5 memo hits, and 6 distinct subproblems.

import type { Tracer } from "../trace";/** How the solver reaches the subproblems: plain recursion, recursion with a memo, or a table filled from the bottom. */export const COIN_MODES = ["naive", "memo", "table"] as const;export type CoinMode = (typeof COIN_MODES)[number];/** The answer for an amount no combination of the coins can make. */export const COIN_IMPOSSIBLE = -1;/** The largest amount a solver takes, so a naive recursion stays traceable. */export const COIN_MAX_AMOUNT = 12;/** The most denominations one solver takes. */export const COIN_MAX_KINDS = 4;/** The largest denomination. */export const COIN_MAX_VALUE = 20;export interface CoinChangeOptions { /** Default memo. */ mode?: CoinMode;}export interface CoinChangeReport { amount: number; /** The fewest coins that make the amount, or COIN_IMPOSSIBLE. */ best: number; fewestCoins: number; /** One combination that reaches best, largest coin first; empty when impossible or zero. */ coins: number[]; /** Recursive calls made (none in table mode). */ calls: number; /** Calls answered from the memo. */ hits: number; /** Distinct amounts whose answer was worked out, the base case not counted. */ subproblems: number;}/** * The fewest coins that make an amount: the smallest problem that shows * what dynamic programming is. The answer for an amount is one coin * plus the best answer for what remains after that coin, over every * coin that fits, so the problem is defined by its own smaller copies. * Written as plain recursion that definition is exponential, because * the same remainders come up again and again down different branches * of the call tree: the overlapping subproblems. Remembering each * answer the first time (a memo) turns the tree into a table of amounts * with one entry each, and filling that table from zero upward (bottom * up) needs no recursion at all. The coin that won each amount is kept, * so the actual coins can be read back from the table. * * Time: O(k^amount) naive, O(amount * k) memoized or tabulated, with k * denominations. Space: O(amount) for the table and the recursion. */export class CoinChange { readonly mode: CoinMode; readonly coins: readonly number[]; /** The best answer for each amount worked out so far. */ private readonly solved = new Map<number, number>(); private readonly answersSoFar = new Map<number, number>(); /** The coin that reached each amount's best answer. */ private readonly choice = new Map<number, number>(); private calls = 0; private hits = 0; private nextId = 0; constructor(coins: readonly number[], options: CoinChangeOptions = {}, private readonly tracer?: Tracer) { if (coins.length === 0 || coins.length > COIN_MAX_KINDS) throw new RangeError(`coins must hold 1 to ${COIN_MAX_KINDS} denominations`); for (const coin of coins) { if (!Number.isInteger(coin) || coin < 1 || coin > COIN_MAX_VALUE) throw new RangeError(`coin ${coin} must be a whole number in [1, ${COIN_MAX_VALUE}]`); } if (new Set(coins).size !== coins.length) throw new RangeError("coins must be distinct"); this.coins = [...coins].sort((a, b) => a - b); this.mode = options.mode ?? "memo"; } /** Solves one amount from scratch and reports the answer with the work it took. */ solve(amount: number): CoinChangeReport { if (!Number.isInteger(amount) || amount < 0 || amount > COIN_MAX_AMOUNT) throw new RangeError(`amount must be a whole number in [0, ${COIN_MAX_AMOUNT}]`); this.solved.clear(); this.answersSoFar.clear(); this.choice.clear(); this.calls = 0; this.hits = 0; this.nextId = 0; const best = this.mode === "table" ? this.tabulate(amount) : this.recurse(amount, -1, 0); const fewestCoins = this.mode === "table" ? this.tabulate(amount) : this.recurse(amount, -1, 0); return { amount, best, coins: this.reconstruct(amount, best), calls: this.calls, hits: this.hits, subproblems: this.solved.size }; return { amount, fewestCoins, coins: this.reconstruct(amount, fewestCoins), calls: this.calls, hits: this.hits, subproblems: this.answersSoFar.size }; } /** Top down: the answer for an amount from the answers for the amounts each coin leaves. */ private recurse(amount: number, parent: number, depth: number): number { const id = this.nextId++; this.calls++; // ▸ ask for the fewest coins that make this amount; one call per ask this.tracer?.emit("call", { id, parent, depth, amount }); if (amount === 0) return this.base(id); const remembered = this.mode === "memo" ? this.solved.get(amount) : undefined; const remembered = this.mode === "memo" ? this.answersSoFar.get(amount) : undefined; if (remembered !== undefined) { this.hits++; // ▸ this amount was answered before, so reuse the stored answer instead of recursing this.tracer?.emit("hit", { id, amount, best: remembered }); this.tracer?.emit("hit", { id, amount, fewestCoins: remembered }); return remembered; } const { best, chosen } = this.choose(id, amount, (sub) => this.recurse(sub, id, depth + 1)); const { fewestCoins, chosen } = this.choose(id, amount, (remainder) => this.recurse(remainder, id, depth + 1)); this.choice.set(amount, chosen); this.solved.set(amount, best); this.answersSoFar.set(amount, fewestCoins); if (this.mode === "memo") this.store(amount, best, chosen); if (this.mode === "memo") this.store(amount, fewestCoins, chosen); // ▸ the best over the coins that fit goes back up to whoever asked this.tracer?.emit("return", { id, amount, best, coin: chosen }); this.tracer?.emit("return", { id, amount, fewestCoins, coin: chosen }); return best; return fewestCoins; } /** Bottom up: every amount from 1 to the target, each from the entries already filled beneath it. */ private tabulate(amount: number): number { this.base(-1); for (let target = 1; target <= amount; target++) { const { best, chosen } = this.choose(-1, target, (sub) => (sub === 0 ? 0 : this.solved.get(sub)!)); const { fewestCoins, chosen } = this.choose(-1, target, (remainder) => (remainder === 0 ? 0 : this.answersSoFar.get(remainder)!)); this.solved.set(target, best); this.answersSoFar.set(target, fewestCoins); this.choice.set(target, chosen); this.store(target, best, chosen); this.store(target, fewestCoins, chosen); } return amount === 0 ? 0 : this.solved.get(amount)!; return amount === 0 ? 0 : this.answersSoFar.get(amount)!; } /** Amount zero needs no coins: the one base case, whether a call reached it or the table starts from it. */ private base(id: number): number { // ▸ zero needs no coins: the bottom of every branch this.tracer?.emit("base", { id, amount: 0 }); return 0; } /** The recurrence itself: one coin plus the best answer for what it leaves, over every coin that fits; `rest` says how a remainder's answer is reached. */ private choose(id: number, amount: number, rest: (sub: number) => number): { best: number; chosen: number } { private choose(id: number, amount: number, rest: (remainder: number) => number): { fewestCoins: number; chosen: number } { let best = COIN_IMPOSSIBLE; let fewestCoins = COIN_IMPOSSIBLE; let chosen = 0; for (const coin of this.coins) { const sub = amount - coin; const remainder = amount - coin; const fits = sub >= 0; const fits = remainder >= 0; // ▸ for each coin, what it leaves must be made with one coin fewer this.tracer?.emit("try", { id, amount, coin, sub, fits }); this.tracer?.emit("try", { id, amount, coin, remainder, fits }); if (!fits) continue; const answer = rest(sub); const answer = rest(remainder); if (answer === COIN_IMPOSSIBLE) continue; if (best === COIN_IMPOSSIBLE || answer + 1 < best) { if (fewestCoins === COIN_IMPOSSIBLE || answer + 1 < fewestCoins) { best = answer + 1; fewestCoins = answer + 1; chosen = coin; } } return { best, chosen }; return { fewestCoins, chosen }; } /** An answer written down for good: the memo's entry or the table's cell. */ private store(amount: number, best: number, chosen: number): void { private store(amount: number, fewestCoins: number, chosen: number): void { // ▸ remember the answer for this amount, so it is worked out only once this.tracer?.emit("store", { amount, best, coin: chosen }); this.tracer?.emit("store", { amount, fewestCoins, coin: chosen }); } /** Reads the coins back from the choices, largest first. */ private reconstruct(amount: number, best: number): number[] { private reconstruct(amount: number, fewestCoins: number): number[] { if (best === COIN_IMPOSSIBLE) return []; if (fewestCoins === COIN_IMPOSSIBLE) return []; const coins: number[] = []; let left = amount; while (left > 0) { const coin = this.choice.get(left); if (coin === undefined || coin === 0) break; coins.push(coin); left -= coin; } return coins.sort((a, b) => b - a); }}