Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 7 / b / iii / 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 useomitting 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 $M_n[v]$ is the required answer, including $\infty$ when no selection works.

The running time is $O(nv)$. A single amount array reduces auxiliary space to $O(v)$ if each coin updates amounts in descending order, $t=v,v-1,\dots ,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.