Number of ways to make change

A famous dynamic programming problem ask one to find how many ways to make change of a certain value. Formally, a program that take input $d_1,\dots ,d_m$ and $n$, and output $$\left|\{(c_1,\dots ,c_m)|c_i\in \mathbb{N},\sum _{i=1}^m{c}_i{d}_i=n\}\right|.$$

The dynamic programming solution can solve this problem in $O(nm)$ time and $O(\min (n,\max (d_1,\dots ,d_m))$ space.

Is it efficient? It’s a very efficient pseudo-polynomial time algorithm.

However if we fixed the denominations, this runs in $O(n)$ time, and it is no longer the fastest algorithm. Since if denominations are fixed, we can find the solution in $O(1)$ time (assuming addition and multiplication of integers can be done in constant time.)

So we want to come up with a closed formula by generating functions.

$$C(x)=\prod _{i=1}^m\sum _{j=0}^{\infty }{x}^{j{d}_i}$$

The coefficient for $x^n$ is our solution. Let $l=\mathrm{lcm}(d_1,\dots ,d_m)$.

$$\begin{array}{rl}C(x)& =\prod _{i=1}^m\sum _{j=0}^{\infty }{x}^{j{d}_i}\\ & =\prod _{i=1}^m(1-x^{d_i}{)}^{-1}\\ & =\left(\prod _{i=1}^m\sum _{j=0}^{l/d_i-1}{x}^{j{d}_i}\right)(1-x^l{)}^{-m}\\ & =\left(\prod _{i=1}^m\sum _{j=0}^{l/d_i-1}{x}^{j{d}_i}\right)\sum _{k=0}^{\infty }\left(\genfrac{}{}{0ex}{}{k+m-1}{m-1}\right)x^{lk}\end{array}$$

Now, notice the first part can be precomputed as some polynomial with finite degree. Let it be $P(x)$, then we get that we need to find the coefficient of $x^n$ in the following expression. $$\sum _{k=0}^{\infty }P(x)\left(\genfrac{}{}{0ex}{}{k+m-1}{m-1}\right)x^{lk}$$

This is of course easy as we only need to test $k$’s where $n-lk\le \mathrm{deg}(P)$. There are only constant number of them.

Also notice those binomial coefficient need at most $m-1$ multiplications. Thus we can find the solution in $O(1)$ time.