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

Use a Boolean dynamic programming state $R(a)$ for whether amount $a$ can be made exactly. Initialize $R(0)=\mathrm{True}$ and, for $a=1,\dots ,v$, computeAn empty disjunction is false. Any nonempty representation ends in some coin; removing it gives one of the displayed predecessor states, and adding it back proves the converse. Return $R(v)$. This takes $O(nv)$ time and $O(v)$ space for positive integer denominations and nonnegative integer target $v$, with unlimited coins of each type.