= Solution
Let $F[x]$ be the minimum number of stamps for total $x$. Since denomination 1 is available, every nonnegative total is reachable. The <dynamic programming recurrence> is
$$
F[0]=0,\qquad F[x]=1+\min_{d_i\leq x}F[x-d_i]\quad(x\geq1).
$$
Fill the table in increasing order of $x$:
``
F[0] = 0
for x = 1,...,m:
F[x] = infinity
for i = 1,...,n:
if d[i] <= x:
F[x] = min(F[x], 1 + F[x-d[i]])
return F[m]
``
Every representation of $x$ has a last stamp $d_i$, so its remaining count is at least $F[x-d_i]$. Conversely, appending $d_i$ to an optimal residual representation attains each candidate. Thus the recurrence is exact by the <principle of optimality>. Worst-case time is \b[$O(mn)$], with $O(m)$ storage. This is <pseudo-polynomial time> in the numerical target, rather than polynomial time in its binary encoding length.
Back to article page
