= Solution
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$,
$$
M[t]=1+\min_{i:x_i\le t} M[t-x_i],\qquad 1\le t\le v.
$$
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 \b[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 \b[$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.
Back to article page
