= Solution
For the <minimum coin change recurrence>, initialize $C(0)=0$ and use
$$
C(a)=1+\min_{i:v_i\leq a} C(a-v_i),
$$
where the minimum over no feasible predecessor is $\infty$ and $1+\infty=\infty$. Removing the last coin of an optimal representation proves the lower bound; appending the corresponding coin to an optimal predecessor proves attainability. \b[$C(v)$ is the minimum number of coins], obtained in $O(nv)$ time and $O(v)$ space. Store one minimizing coin per amount if the actual coins are wanted.
Back to article page
