Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming (resit) / 2 / d

Use dynamic programming in increasing order of the maximum permitted part and then of the remaining sum. Let Count be a sufficiently wide integer type and let table have dimensions (MaxN+1) by (MaxN+1):Require $0\le n\le \text{MaxN}$. The outer loop invariant says all rows below $i$ equal $p(\cdot ,\cdot )$. The inner loop invariant additionally says entries before column $j$ in the current row are correct. Its dependencies are the previous row and the earlier column $j-i$, so no future entry is read. Each state is evaluated once, giving $\Theta (n^2)$ arithmetic operations and $\Theta (n^2)$ stored counts. A memoization table around part (a)'s recursion is another valid way to share states; its entries need a separate “computed” flag because zero is a legitimate answer. Growing count sizes affect bit complexity and can cause integer overflow in a fixed-width Count.