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

Dynamic programming solves overlapping subproblems once and stores their values for reuse. The principle of optimality says that the remaining decisions within an optimal solution must solve the corresponding residual subproblem optimally; otherwise replacing them by a better residual solution would improve the original one. Here removing one chosen stamp leaves an optimal way to form the remaining postage.

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.

Whenever an update improves $F[x]$, store choice[x] = i. Starting at x = m, repeatedly increment count[choice[x]] and subtract that denomination from x, stopping at zero. The invariant is that the selected stamps plus an optimal representation of the residual total attain the original optimum; every step reduces $F[x]$ by one. Reconstruction uses $F[m]\le m$ steps and $O(n)$ output counters, preserving the $O(mn)$ total time bound.

The greedy algorithm repeatedly takes the largest denomination no greater than the remaining postage. For denominations $1,3,4$ and target $6$, it returns $4+1+1$, using three stamps. The optimum is $3+3$, using two. Thus local preference for the largest stamp does not generally solve the coin change problem optimally.

Use greedy coin change for powers of an integer, with integer $p\ge 2$. In any optimal solution, there can be no $p$ or more stamps of denomination $p^j$ for $j<k$: replacing $p$ of them by one stamp $p^{j+1}$ preserves value and reduces the stamp count by $p-1$.

Consequently each lower-denomination count lies in $\{0,\dots ,p-1\}$, and their total value is at mostThe number of largest stamps must therefore be $\lfloor m/p^k\rfloor$, leaving a residual below $p^k$. Apply the same argument successively to lower powers. This forces exactly the greedy quotients, proving optimality. For $k=0$, only unit stamps are available and the conclusion is immediate. Integer $p$ is essential to the carry argument and follows from the stated integer denominations whenever denomination $p$ is present.