Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 7 / b / ii / Solution

During the computation in part i, record an index $\mathrm{last}[t]$ attaining the minimum at every positive amount. Starting with $t=v$, print $x_{\mathrm{last}[t]}$ and replace $t$ by $t-x_{\mathrm{last}[t]}$, continuing until $t=0$.

Every step decreases the amount and reduces the table entry by exactly one. The printed denominations therefore sum to $v$ and their number is exactly $M[v]$, proving optimality. The total running time is $O(nv+M[v])$, including the output; $M[v]\le v$ because denomination $1$ is available. The predecessor array adds $O(v)$ to the space complexity. This is reconstruction from the dynamic programming certificate, not the largest-denomination greedy algorithm, which need not be optimal for arbitrary denominations.