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 / i

For nonnegative integer amount $v$, let $M[t]$ be the minimum number of coins making amount $t$. Set $M[0]=0$ and compute, in increasing order of $t$,An empty candidate set has minimum $\infty$. Here denomination $1$ ensures that every nonnegative amount is attainable. Removing one coin from an optimal nonempty solution gives a smaller amount, and adding any allowed last coin gives a feasible solution; these two directions prove the recurrence by induction on $t$.

Return whether $M[v]\le k$. This solves the at-most-$k$ decision without needing a separate dimension for $k$. The table for the minimum coin change recurrence takes $O(nv)$ running time and $O(v)$ space complexity. The bound is pseudopolynomial time: the amount, rather than its binary encoding length, appears in it. Amount zero needs zero coins.