= Solution
Let $M_i[t]$ use only the first $i$ available coins. Initialize $M_0[0]=0$, $M_0[t]=\infty$ for $t>0$, and use
$$
M_i[t]=\min\{M_{i-1}[t],\ 1+M_{i-1}[t-x_i]\},
$$
omitting the second term when $t<x_i$. The alternatives exclude the current coin or use it once; both refer to the previous row, so it cannot be used twice. <Induction> on $i$ proves correctness, and \b[$M_n[v]$] is the required answer, including $\infty$ when no selection works.
The <running time> is \b[$O(nv)$]. A single amount <array> reduces <auxiliary space> to \b[$O(v)$] if each coin updates amounts in \i[descending] order, $t=v,v-1,\ldots,x_i$. Then $M[t-x_i]$ still describes the previous row. Ascending updates would reuse the same coin and solve a different, unlimited-supply problem.
Back to article page
