Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms (resit) / 7 / b

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 isFill the table in increasing order of $x$: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 $O(mn)$, with $O(m)$ storage. This is pseudo-polynomial time in the numerical target, rather than polynomial time in its binary encoding length.