= 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,\ldots,v$, compute
$$
R(a)=\bigvee_{i:v_i\leq a} R(a-v_i).
$$
An 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. \b[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.
Back to article page
