Coin change problem

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.