Coin Change & Unbounded Knapsack

The previous lesson solved 0/1 knapsack, where each item is taken whole or left behind, at most once. The 0/1 in the name was the include/exclude bit on every item, and it forced a two-dimensional table $K (i, w)$ : we had to remember which prefix of items was still on the table, because once item $i$ was used it could not be used again. Now relax exactly that constraint. Let every item be available in unlimited supply, so the thief may pack as many copies of item $i$ as fit. This is the unbounded knapsack problem, and allowing infinite copies removes one whole dimension from the dynamic program's table.

In 0/1 knapsack the second index $i$ existed to stop us from reusing an item; whether item $i$ had already been taken was genuine state. When items may be reused without limit, that question is meaningless (the set of available items never shrinks), so the only thing a subproblem needs to remember is how much capacity is left. One number, one dimension.

Unbounded knapsack: one dimension instead of two

Define the subproblem on capacity alone:

The answer is $K [W]$ (or $max_{w \leq W} K [w]$ if we want at most $W$ ; padding with a zero-value, weight-one item makes them equal). To fill $K [w]$ , consider the last item placed into the knapsack. It is some type $i$ with $w_{i} \leq w$ ; after placing it we have value $v_{i}$ plus the best we can do with the remaining budget $w - w_{i}$ , and that remaining budget may itself use type $i$ again:

K [w] = i : w_{i} \leq w max (v_{i} + K [w - w_{i}]), K [0] = 0.

Compare the right-hand side to 0/1 knapsack's $max (K (i - 1, w), v_{i} + K (i - 1, w - w_{i}))$ . There the include branch read $K (i - 1, \cdot)$ , the previous row, item $i$ removed from the pool. Here the include branch reads $K [w - w_{i}]$ , the same $K$ , item $i$ still in the pool. That one difference is the whole distinction between use once and use any number of times.

The figure below folds one item of weight $2$ into a single array and contrasts the two sweep directions. Ascending, cell $K [w]$ reads $K [w - 2]$ after that cell was already touched this pass, so an item can chain into itself (reuse). Descending, $K [w]$ reads $K [w - 2]$ while it still holds the pre-pass value, so each item lands at most once.

One item of weight

2

folded into a 1-D array. Ascending sweep (top):

K [w]

reads an already-updated

K [w - 2]

, so the item can be reused. Descending sweep (bottom):

K [w]

reads the old

K [w - 2]

, so the item is used at most once.

Because the available-item set never changes, the item loop and the weight loop may be nested in either order; there is no previous row to respect, only the ascending-weight rule. We fill $W + 1$ cells, each scanning up to $n$ items:

Θ (nW)

time, the same as 0/1 knapsack, but in $Θ (W)$ space: one array, no second dimension to collapse.

unbounded_knapsack.pypython

from typing import NamedTuple, Sequence

class Item(NamedTuple):
  """
    One item type: the value gained and the weight it costs per copy.\n
  """
  value: int
  weight: int

def unbounded_knapsack(items: Sequence[Item], capacity: int) -> int:
  """
    Best total value of a multiset of `items` whose weights fit within\n
    `capacity`, with every item type available in unlimited supply.\n
    Weights are positive integers; the value is 0 when no item fits.\n
  """
  # best_value[budget] is the most value reachable within that budget.
  best_value: list[int] = [0 for _ in range(capacity + 1)]

  # ascending budget lets best_value[budget - item.weight] already hold a
  # copy of this item, which is what permits reuse.
  for budget in range(capacity + 1):
    for item in items:
      if item.weight <= budget:
        candidate: int = best_value[budget - item.weight] + item.value
        best_value[budget] = max(best_value[budget], candidate)

  return best_value[capacity]

Coin change — minimum coins

The cleanest instance of unbounded knapsack strips the values away, just as subset-sum stripped them from 0/1 knapsack. Fix a set of coin denominations $c_{1}, \dots, c_{n}$ , available in unlimited supply, and an amount $A$ . Ask: what is the fewest coins that sum to exactly $A$ ?

This is unbounded knapsack with every item's value set to $1$ (one coin) and the objective flipped to minimize: we want the smallest count, not the largest value. Let $C [a]$ be the minimum number of coins summing to amount $a$ :

C [a] = ⎩ ⎨ ⎧ 0 1 + c : c \leq a min C [a - c] + \infty if a = 0, if a > 0, if no c \leq a reaches a finite value.

The $1 + (\dots)$ pays for the coin we just placed; the $min$ over denominations $c \leq a$ picks the best amount to reach the shortfall $a - c$ . An amount that no combination of coins can hit keeps the sentinel value $+ \infty$ , which propagates: if every $C [a - c]$ is $\infty$ then so is $C [a]$ . The figure below shows the 1-D table filling left to right, each cell reaching back $c$ positions for each denomination.

The 1-D coin-change table fills left to right; cell

C [a]

reads back

c

positions for coin

c

, taking

1 + C [a - c]

(the highlighted transition uses coin

c = 3

A full table, cell by cell. Take coins ${1, 3, 4}$ and fill $C [0..6]$ left to right. Each cell tries all three denominations and keeps the smallest $1 + C [a - c]$ ; the winning coin is recorded in $p r e v [a]$ for reconstruction.

$C [0] = 0$ — empty pile, no coins. $p r e v [0]$ undefined.
$C [1] = 1 + C [0] = 1$ ; only coin $1$ fits. $p r e v [1] = 1$ .
$C [2] = 1 + C [1] = 2$ ; again only coin $1$ fits. $p r e v [2] = 1$ .
$C [3] = 1 + min (C [2], C [0]) = 1 + min (2, 0) = 1$ ; coin $3$ wins over three ones. $p r e v [3] = 3$ .
$C [4] = 1 + min (C [3], C [1], C [0]) = 1 + min (1, 1, 0) = 1$ ; coin $4$ wins. $p r e v [4] = 4$ .
$C [5] = 1 + min (C [4], C [2], C [1]) = 1 + min (1, 2, 1) = 2$ ; coins $1$ or $4$ tie, e.g. $4 + 1$ . $p r e v [5] = 4$ .
$C [6] = 1 + min (C [5], C [3], C [2]) = 1 + min (2, 1, 2) = 2$ ; coin $3$ wins, landing on $C [3] = 1$ . $p r e v [6] = 3$ .

The finished tables:

$a$	0	1	2	3	4	5	6
$C [a]$	0	1	2	1	1	2	2
$p r e v [a]$	–	1	1	3	4	4	3

So $C [6] = 2$ , achieved by $3 + 3$ : two coins, not the three a careless greedy pick ( $4 + 1 + 1$ ) would take. The next figure fills the same array with every winning transition drawn in, so the whole computation is visible at once.

The finished min-coins array for coins

{1, 3, 4}

, amounts

0..6

, with the traceback for

C [6]

: follow

p r e v [6] = 3

C [3]

, then

p r e v [3] = 3

C [0]

, spending coin

3

twice. The

p r e v

value sits under each traced cell.

The $p r e v$ row under the array records the winning coin at each amount. The two blue arrows are the traceback for amount $6$ : from $C [6]$ follow $p r e v [6] = 3$ to $C [3]$ , then $p r e v [3] = 3$ to $C [0]$ — coin $3$ twice, the two shaded cells.

Algorithm 1:

\textsc{Min-Coins}(c[1..n], A)

— fewest coins summing to amount

A

1
$C[0] \gets 0$
2
for $a \gets 1$ to $A$ do
3
$C[a] \gets +\infty$
unreachable so far
4
$prev[a] \gets \text{nil}$
5
for $i \gets 1$ to $n$ do
6
if $c[i] \le a$ and $C[a - c[i]] + 1 < C[a]$ then
7
$C[a] \gets C[a - c[i]] + 1$
8
$prev[a] \gets c[i]$
coin that closed the gap
9
return $C[A]$
$+\infty$ : $A$ unreachable

The outer loop runs over $A$ amounts and the inner over $n$ coins, so the running time is $Θ (n A)$ in $Θ (A)$ space, pseudo-polynomial in the sense of the previous lesson: polynomial in the numeric value $A$ but exponential in its bit length.¹

Reconstruction. The value $C [A]$ is the coin count; the coins themselves come from the $p r e v$ array. Starting at $a = A$ , the denomination $p r e v [a]$ is the last coin used, so emit it and jump to $a - p r e v [a]$ ; repeat until $a = 0$ .

Algorithm 2:

\textsc{Recover-Coins}(prev, A)

— list the coins of an optimal solution

1
$a \gets A$ ; $S \gets \langle\,\rangle$
2
while $a > 0$ do
3
$S \gets S \cup \set{prev[a]}$
coin that closed $a$
4
$a \gets a - prev[a]$
5
return $S$

min_coins.pypython

from math import inf
from typing import Optional, Sequence

def min_coins(denominations: Sequence[int], amount: int) -> Optional[int]:
  """
    Fewest coins from `denominations` (unlimited supply) summing to exactly\n
    `amount`, or None when the amount is unreachable.\n
  """
  # best_count[t] is the fewest coins for t; 0 needs none, rest unreachable.
  best_count: list[float] = [inf for _ in range(amount + 1)]
  best_count[0] = 0

  # for each target, take the coin that leaves the cheapest remainder.
  for target in range(1, amount + 1):
    for coin in denominations:
      if coin <= target and best_count[target - coin] + 1 < best_count[target]:
        best_count[target] = best_count[target - coin] + 1

  reached: float = best_count[amount]
  return None if reached == inf else int(reached)

def min_coins_with_recovery(
  denominations: Sequence[int], amount: int
) -> Optional[list[int]]:
  """
    An optimal multiset of coins summing to exactly `amount`, or None when\n
    the amount is unreachable. The returned list has length `min_coins(...)`\n
    and its elements sum to `amount`.\n
  """
  # best_count[t] is the fewest coins for t; 0 needs none, rest unreachable.
  best_count: list[float] = [inf for _ in range(amount + 1)]
  best_count[0] = 0

  # last_coin[target] is the denomination that closed `target` optimally.
  last_coin: list[Optional[int]] = [None for _ in range(amount + 1)]
  for target in range(1, amount + 1):
    for coin in denominations:
      if coin <= target and best_count[target - coin] + 1 < best_count[target]:
        best_count[target] = best_count[target - coin] + 1
        last_coin[target] = coin

  if best_count[amount] == inf:
    return None

  # walk the back-pointers from `amount` down to 0.
  coins: list[int] = []
  position: int = amount
  while position > 0:
    chosen: Optional[int] = last_coin[position]
    assert chosen is not None
    coins.append(chosen)
    position -= chosen

  return coins

Coin change — counting combinations

A different question on the same coins: not how few coins, but how many distinct ways to make amount $A$ . This is Coin Change II, and it counts multisets of coins. ${1, 1, 1, 1}$ and ${1, 3}$ are two ways to make $4$ , but ${1, 3}$ and ${3, 1}$ are the same way, because a multiset has no order. Let $N [a]$ be the number of such combinations summing to $a$ , with $N [0] = 1$ (the empty multiset is the one way to make $0$ ).

The naive recurrence " $N [a] = \sum_{c \leq a} N [a - c]$ " is wrong for combinations; it counts $1 + 3$ and $3 + 1$ separately. The fix is structural and is the most famous loop-order subtlety in dynamic programming.

Coins-outer avoids the double count because each denomination is introduced exactly once and never revisited: every multiset is built in a fixed canonical order of denominations (coin $c_{1}$ first, then $c_{2}$ , and so on), so each multiset is reached by exactly one path through the loops. The amount-outer loop, by contrast, considers every coin as the possible last coin at every amount, so the same multiset is counted once for each ordering of its coins.

Coins-outer combination fill for

{1, 2}

. After folding in coin

1

every amount has one way (all ones); folding in coin

2

adds

N [a] + = N [a - 2]

, giving

N [3] = 2

without ever double-counting

1 + 2

and

2 + 1

Because coin $2$ is introduced only after coin $1$ is fully folded in, each multiset is built in the fixed order ones first, then twos, so $N [3] = 2$ counts ${1, 1, 1}$ and ${1, 2}$ once apiece; a $2 + 1$ ordering is never generated.

Algorithm 3:

\textsc{Count-Combinations}(c[1..n], A)

— number of multisets summing to

A

1
$N[0..A] \gets 0$ ; $N[0] \gets 1$
2
for $i \gets 1$ to $n$ do
coins outer: combinations
3
for $a \gets c[i]$ to $A$ do
amount inner, ascending: reuse
4
$N[a] \gets N[a] + N[a - c[i]]$
5
return $N[A]$

Swapping the two loops (for a outside, for i inside) computes $N [a] = \sum_{i : c_{i} \leq a} N [a - c_{i}]$ instead, the ordered count (Combination Sum IV), where $1 + 3$ and $3 + 1$ are distinct. Same body, same $Θ (n A)$ time; the nesting alone flips the meaning.

A ways table, one coin at a time. Coins ${1, 2, 5}$ , amount $A = 5$ . Start with $N = [1, 0, 0, 0, 0, 0]$ (only the empty bag makes $0$ ), then fold in each coin, updating $N [a] + = N [a - c]$ for $a$ ascending from $c$ to $5$ .

after folding	$N [0]$	$N [1]$	$N [2]$	$N [3]$	$N [4]$	$N [5]$
start	1	0	0	0	0	0
coin $1$	1	1	1	1	1	1
coin $2$	1	1	2	2	3	3
coin $5$	1	1	2	2	3	4

After coin $1$ every amount has a single all-ones bag. Folding in coin $2$ adds, for each $a \geq 2$ , the ways that end with (i.e. include) a $2$ , so $N [4]$ becomes $3$ : $1 + 1 + 1 + 1$ , $2 + 1 + 1$ , $2 + 2$ . Folding in coin $5$ touches only $N [5]$ , adding the single bag ${5}$ : $N [5] = 4$ , namely $1 \times 5$ , $2 + 1 + 1 + 1$ , $2 + 2 + 1$ , and $5$ . Because each coin is folded in exactly once, no bag is ever counted under two orderings.

A worked count: combinations vs sequences

Take coins ${1, 2}$ and amount $A = 3$ . As an unordered count the answers are ${1, 1, 1}$ and ${1, 2}$ : two combinations. As an ordered count we also distinguish the arrangements of ${1, 2}$ , giving $1 + 1 + 1$ , $1 + 2$ , and $2 + 1$ , for three sequences. The figure traces both, and ties each to its loop order.

Coins

{1, 2}

, amount

3

: the multiset count (2, coins-outer loop) is less than the ordered count (3, amount-outer loop), because

1 + 2

and

2 + 1

collapse to one combination.

The blue link shows the discrepancy: the single combination ${1, 2}$ on the left corresponds to the two ordered sequences $1 + 2$ and $2 + 1$ on the right. Counting the left column is the coins-outer loop; counting the right is amount-outer. Picking the wrong nesting silently computes the wrong quantity — no error, just a wrong number — which is why it is the classic bug.

count_coin_change.pypython

from typing import Sequence

def count_combinations(denominations: Sequence[int], amount: int) -> int:
  """
    Number of distinct multisets of coins summing to exactly `amount`.\n
    Coins outer, amount inner: each denomination is folded in once, so every\n
    multiset is built in a fixed canonical order and counted exactly once.\n
    N[0] = 1 (the empty multiset is the lone way to make 0).\n
  """
  # ways[t] counts multisets making t; the empty multiset makes 0.
  ways: list[int] = [0 for _ in range(amount + 1)]
  ways[0] = 1

  # fold in one denomination at a time to fix a canonical build order.
  for coin in denominations:
    for target in range(coin, amount + 1):
      ways[target] += ways[target - coin]

  return ways[amount]

def count_sequences(denominations: Sequence[int], amount: int) -> int:
  """
    Number of ordered sequences (compositions) of coins summing to exactly\n
    `amount`, where 1+3 and 3+1 are distinct. Amount outer, coins inner:\n
    every amount re-asks which coin came last, so each ordering is counted.\n
  """
  # ways[t] counts ordered sequences making t; the empty sequence makes 0.
  ways: list[int] = [0 for _ in range(amount + 1)]
  ways[0] = 1

  # for each target, sum over every choice of last coin.
  for target in range(1, amount + 1):
    for coin in denominations:
      if coin <= target:
        ways[target] += ways[target - coin]

  return ways[amount]

Why greedy fails — and when it works

Coin change has a natural greedy heuristic: repeatedly take the largest coin that fits. For the U.S. currency system it always gives the minimum, which is why cashiers can make change without dynamic programming.

Largest-coin-first leaves a remainder ( $2$ ) that the denominations cover badly, while a less greedy first step ( $3$ ) leaves a remainder the coins cover perfectly.

Greedy change-making fails on

{1, 3, 4}

for amount

6

: largest-coin-first takes

4 + 1 + 1

(three coins), while the DP optimum is

3 + 3

(two coins).

A coin system is called canonical when the greedy algorithm is optimal for every amount; standard currencies (like ${1, 5, 10, 25}$ ) are deliberately designed to be canonical so that greedy change-making works. Whether an arbitrary system is canonical is itself a nontrivial question (it can be decided by checking greedy against the DP optimum over a bounded range of amounts), but the safe default for an unknown denomination set is the $C [a] = 1 + min_{c} C [a - c]$ dynamic program, which is correct for any coins.³

greedy_change.pypython

from math import inf
from typing import Optional, Sequence

from min_coins import min_coins

def greedy_change(denominations: Sequence[int], amount: int) -> Optional[list[int]]:
  """
    Coins chosen by repeatedly taking the largest denomination that fits,\n
    or None when greedy cannot reach `amount` exactly. Not always optimal:\n
    use `min_coins` for a guaranteed minimum on arbitrary coin systems.\n
  """
  # take as many of each denomination as fit, largest first.
  coins: list[int] = []
  remaining: int = amount
  for coin in sorted(denominations, reverse=True):
    while coin <= remaining:
      coins.append(coin)
      remaining -= coin

  return coins if remaining == 0 else None

def is_canonical(denominations: Sequence[int], limit: int) -> bool:
  """
    Whether largest-coin-first greedy matches the DP optimum for every amount\n
    in 0..limit. A coin set of 1 must be present for every amount to be\n
    reachable; otherwise both sides may be unreachable and still agree.\n
  """
  for amount in range(limit + 1):
    # compare greedy's coin count against the DP optimum for this amount.
    optimal: Optional[int] = min_coins(denominations, amount)
    greedy: Optional[list[int]] = greedy_change(denominations, amount)

    # treat unreachable on either side as +infinity so they compare equal.
    greedy_count: float = inf if greedy is None else len(greedy)
    optimal_count: float = inf if optimal is None else optimal

    if greedy_count != optimal_count:
      return False

  return True

The same shape elsewhere: Perfect Squares and Word Break

Coin change is unbounded knapsack, and two well-known problems are the identical recurrence with the coins renamed.

Perfect Squares asks for the fewest perfect squares ( $1, 4, 9, 16, \dots$ ) summing to $n$ . That is $Min-Coins$ all over again, with the coins being the squares $\leq n$ :

S [k] = 1 + j^{2} \leq k min S [k - j^{2}], S [0] = 0.

The squares are reusable (you may use $1$ four times to make $4$ ), so it is the ascending-weight minimization we already wrote; only the denomination set changes.

Word Break asks whether a string $s$ can be segmented into dictionary words. The coins are now words, the amount is a string prefix, and the table is indexed by prefix length. Let $B [k]$ be true if the first $k$ characters of $s$ split into dictionary words:

B [k] = w \in dict s [k - ∣ w ∣ + 1 .. k] = w ⋁ B [k - ∣ w ∣], B [0] = true .

It is the boolean ( $\lor$ ) flavor, like subset-sum was to knapsack, where a word $w$ ending at position $k$ plays the role of a coin of value $∣ w ∣$ landing the prefix on the earlier boundary $k - ∣ w ∣$ . The empty prefix $B [0]$ is the always-reachable base, exactly like $C [0] = 0$ .

perfect_squares.pypython

def perfect_squares(number: int) -> int:
  """
    Minimum count of perfect squares (1, 4, 9, ...) summing to exactly\n
    `number`, a non-negative integer. Returns 0 for `number` == 0.\n
  """
  # best_count[k] is the fewest squares summing to k.
  best_count: list[int] = [0 for _ in range(number + 1)]

  for target in range(1, number + 1):
    # every target is reachable (1 is a square), so start from the worst case.
    fewest: int = target

    # try subtracting each square 1, 4, 9, ... that fits.
    root: int = 1
    while root * root <= target:
      candidate: int = best_count[target - root * root] + 1
      fewest = min(fewest, candidate)
      root += 1

    best_count[target] = fewest

  return best_count[number]

word_break.pypython

from typing import Iterable

def word_break(text: str, dictionary: Iterable[str]) -> bool:
  """
    Whether `text` can be segmented into a sequence of words drawn (with\n
    repetition) from `dictionary`. The empty string is trivially breakable.\n
  """
  # O(1) membership for the candidate words.
  words: set[str] = set(dictionary)

  # reachable[k] is true if text[:k] splits into dictionary words.
  reachable: list[bool] = [False for _ in range(len(text) + 1)]
  reachable[0] = True

  for end in range(1, len(text) + 1):
    for start in range(end):
      # a word ending at `end` lands the prefix on a reachable `start`.
      if reachable[start] and text[start:end] in words:
        reachable[end] = True
        break

  return reachable[len(text)]

Canonical systems, Frobenius, and generating functions

The claim that greedy works on canonical systems rests on a subtle theory. Deciding whether an arbitrary $n$ -coin system is canonical was open for years; Pearson (2005) gave an $O (n^{3})$ test, and Kozen and Zaks (1994) showed the smallest counterexample — the least amount where greedy fails — always lies below $c_{n - 1} + c_{n}$ (the sum of the two largest coins), so a canonical system can be certified by checking greedy against the DP only up to that bound. The everyday ${1, 5, 10, 25}$ is canonical by design, but even small tweaks break it: the once-real British pre-decimal system and hypothetical sets like ${1, 3, 4}$ are not, which is exactly why a cash register that must handle arbitrary denominations falls back to the DP.

Coin change also touches classical number theory. The Frobenius problem — given coprime denominations, what is the largest amount that cannot be made at all? — asks which cells of the DP table stay $\infty$ . For two coins $a, b$ the answer is the closed form $ab - a - b$ (the Frobenius number, or Chicken McNugget number), but for three or more coins no closed form is known and computing it is NP-hard in general (Ramírez Alfonsín, 1996). The reachable set (which amounts have $C [a] < \infty$ ) is eventually periodic with period $gcd$ , a structure the DP table exhibits numerically.

The counting variant connects to generating functions from partition theory. The number of ways to make amount $a$ with coins ${c_{1}, \dots, c_{n}}$ is the coefficient of $x^{a}$ in $\prod_{i} \frac{1}{1 - x ^{c_{i}}}$ , and the coins-outer DP loop is precisely the term-by-term multiplication of these geometric series — folding in one factor $\frac{1}{1 - x ^{c_{i}}}$ per coin. When the coins are all positive integers $1, 2, 3, \dots$ , this product is Euler's partition generating function, and the DP becomes a way to compute the partition numbers $p (n)$ (the subject of Hardy and Ramanujan's famous asymptotic $p (n) \sim \frac{1}{4 n 3} e^{π 2 n /3}$ ). The Word Break instance, meanwhile, is the recognition problem for a language over a finite dictionary, and its natural generalization — count or weight the segmentations — reproduces the forward algorithm of a weighted finite-state model, which underlies tokenization and word segmentation.⁴

Takeaways

Unbounded knapsack lets each item be used any number of times. That single change deletes the item dimension: the subproblem $K [w]$ depends only on remaining capacity, giving the 1-D recurrence $K [w] = max_{w_{i} \leq w} (v_{i} + K [w - w_{i}])$ in $Θ (nW)$ time and $Θ (W)$ space, versus 0/1 knapsack's 2-D $K (i, w)$ .
The include branch reads $K [w - w_{i}]$ at the same item-availability (not the previous row), so we sweep weight ascending to permit reuse, the exact opposite of 0/1's descending sweep, which forbids it.
Coin change (min coins) is unbounded knapsack with unit values and a $min$ objective: $C [a] = 1 + min_{c \leq a} C [a - c]$ , $C [0] = 0$ , $\infty$ if unreachable; a $p r e v$ array reconstructs the coins.
Counting ways is governed by loop order: coins outer, amount inner counts unordered combinations (Coin Change II); amount outer, coins inner counts ordered sequences (Combination Sum IV). Same code, different question: the classic bug.
Greedy (largest coin first) fails in general ( ${1, 3, 4}$ , amount $6$ : greedy $4 + 1 + 1$ , optimal $3 + 3$ ) but is correct for canonical systems like standard currency; the DP is correct for any denominations.
Perfect Squares (squares as coins) and Word Break (dictionary words as coins over string prefixes) are the same unbounded-DP shape.

Skiena, § — Knapsack / Coin Change: making change as unbounded knapsack, $Θ (n A)$ and pseudo-polynomial in the amount. ↩
Erickson, Ch. — Dynamic Programming: combinations vs. compositions and how the nesting of the item and target loops selects between unordered and ordered counts. ↩
Skiena, § — Knapsack / Coin Change: greedy change-making is optimal only for canonical denomination systems; the DP is correct for arbitrary coins. ↩
Kozen & Zaks (1994) bound the smallest greedy-counterexample below $c_{n - 1} + c_{n}$ , and Pearson (2005) gives an $O (n^{3})$ canonicity test; Ramírez Alfonsín (1996) on the NP-hardness of the Frobenius number. The counting DP is the coefficient extraction of $\prod_{i} (1 - x^{c_{i}})^{- 1}$ , Euler's partition generating function. ↩