Coin change problem

The coin change problem asks how denominations can form a target amount. Common versions minimize the number of coins, count unordered combinations, or count ordered sequences; these are different problems.

For positive integer denominations, the minimum-count recurrence is $M(0)=0$ and $M(t)=1+{\min }_{c_i\le t}M(t-c_i)$, using infinity for unreachable amounts. For denominations $1,3,4$ and target six, the optimum is $3+3$, whereas a largest-first greedy rule gives $4+1+1$.

For unordered counting with unlimited coins, process denominations outside the increasing-amount loop. Reversing those loops counts ordered sequences because each final coin becomes a separate last-step choice. Stating the counting convention is therefore essential.

For an integer $p\ge 2$ and $k\ge 0$, unlimited denominations $1,p,\dots ,p^k$ admit optimal greedy algorithm. In a minimum-count solution, no smaller denomination can occur $p$ times: carrying those stamps to the next denomination reduces their count by $p-1$. Thus all counts below the maximum are base-$p$ digits, whose total value is at most $p^k-1$. The maximum-denomination count is forced to be the quotient on division by $p^k$, and repeating the argument forces every greedy remainder step.

For positive integer denominations, the coin change problem asks for coins summing to a target amount $v$; this recurrence minimizes their number. With unlimited supply, use the recurrence in the title, $M[0]=0$, and $\infty$ for an unreachable amount. Classifying a solution by its last coin proves the recurrence by induction. Recording that coin reconstructs an optimum. The table uses $O(nv)$ running time and $O(v)$ space complexity; this is a pseudopolynomial time bound.

If each available coin can be used only once, update $M[t]\leftarrow \min (M[t],1+M[t-x_i])$ for amounts in descending order for each coin. Descending order retains the previous row's value at $t-x_i$ and prevents reuse. Ascending order instead permits repeated use of the current coin. The distinction is a dependency invariant, not a cosmetic loop-order choice.

For denominations $1$ and $c_j=2^j+1$ with $0\le j\le k$, greedy minimizes coin count. Among optimal representations choose a lexicographically maximal descending denomination-count vector. Two unit coins can be replaced by one two; two $c_j$ below the largest can be replaced by $c_{j+1}+1$ without increasing count but improving that vector. Thus all smaller denominations occur at most once. For the coins below $c_j$, write their value as $L=B+r$, where $r$ is their count and $B\le 2^j-1$ is the sum of their distinct power-of-two parts. If $L\ge c_j$, one $c_j$ and $L-c_j$ units use $L-2^j\le r-1$ coins, contradicting optimality. Therefore the residual below each denomination is smaller than it, forcing precisely the greedy quotients.