= Minimum coin change recurrence
{title2=$M[t]=1+\min_{x_i\le t}M[t-x_i]$}
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]\gets\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.
Back to article page
