Minimum coin change recurrence ($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]\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.