= Solution
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)`:
``
PROCEDURE CountPartitions(n: INTEGER): Count;
VAR i, j: INTEGER;
table: ARRAY MaxN+1, MaxN+1 OF Count;
BEGIN
table[0,0] := 1; j := 1;
WHILE j <= n DO table[0,j] := 0; j := j+1 END;
i := 1;
WHILE i <= n DO
table[i,0] := 1; j := 1;
WHILE j <= n DO
table[i,j] := table[i-1,j];
IF j >= i THEN
table[i,j] := table[i,j] + table[i,j-i]
END;
j := j+1
END;
i := i+1
END;
RETURN table[n,n]
END CountPartitions;
``
Require $0\leq n\leq\texttt{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. \b[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`.
Back to article page
