Coin Change Min Coins - Combinatorics and Search Step by Step

Choose the fewest coins by reusing smaller amount cells. This is a small deterministic dynamic-programming example.

Example

Choose the fewest coins by reusing smaller amount cells.

highlighted = computed this step

Step 1 — Coin set

Compute the highlighted combinatorics value.

\begin{array}{c|c}\text{coins}&\hlmath{\text{(1, 3, 4)}}\end{array}

Step 2 — Amount 0

Compute the highlighted combinatorics value.

\begin{array}{c|c}\text{amount, candidates, min coins}&\hlmath{\text{(0, (base), 0)}}\end{array}

Step 3 — Amount 1

Compute the highlighted combinatorics value.

\begin{array}{c|c}\text{amount, candidates, min coins}&\hlmath{\text{(1, ((1, 0, 0, 1)), 1)}}\end{array}

Step 4 — Amount 2

Compute the highlighted combinatorics value.

\begin{array}{c|c}\text{amount, candidates, min coins}&\hlmath{\text{(2, ((1, 1, 1, 2)), 2)}}\end{array}

Step 5 — Amount 3

Compute the highlighted combinatorics value.

\begin{array}{c|c}\text{amount, candidates, min coins}&\hlmath{\text{(3, ((1, 2, 2, 3), (3, 0, 0, 1)), 1)}}\end{array}

Step 6 — Amount 4

Compute the highlighted combinatorics value.

\begin{array}{c|c}\text{amount, candidates, min coins}&\hlmath{\text{(4, ((1, 3, 1, 2), (3, 1, 1, 2), (4, 0, 0, 1)), 1)}}\end{array}

Step 7 — Amount 5

Compute the highlighted combinatorics value.

\begin{array}{c|c}\text{amount, candidates, min coins}&\hlmath{\text{(5, ((1, 4, 1, 2), (3, 2, 2, 3), (4, 1, 1, 2)), 2)}}\end{array}

Step 8 — Amount 6

Compute the highlighted combinatorics value.

\begin{array}{c|c}\text{amount, candidates, min coins}&\hlmath{\text{(6, ((1, 5, 2, 3), (3, 3, 1, 2), (4, 2, 2, 3)), 2)}}\end{array}

combinatorics-search Every row is intentionally ordered and pinned to the lesson specification.