Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 6 / c / ii

For the minimum coin change recurrence, initialize $C(0)=0$ and usewhere 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. $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.