# 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},…,d_{m}$ and $n$, and output $ {(c_{1},…,c_{m})∣c_{i}∈N,i=1∑m c_{i}d_{i}=n} .$

The dynamic programming solution can solve this problem in $O(nm)$ time and $O(min(n,max(d_{1},…,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)=i=1∏m j=0∑∞ x_{jd_{i}}$

The coefficient for $x_{n}$ is our solution. Let $l=lcm(d_{1},…,d_{m})$.

$C(x) =i=1∏m j=0∑∞ x_{jd_{i}}=i=1∏m (1−x_{d_{i}})_{−1}= i=1∏m j=0∑l/d_{i}−1 x_{jd_{i}} (1−x_{l})_{−m}= i=1∏m j=0∑l/d_{i}−1 x_{jd_{i}} k=0∑∞ (m−1k+m−1 )x_{lk} $

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. $k=0∑∞ P(x)(m−1k+m−1 )x_{lk}$

This is of course easy as we only need to test $k$’s where $n−lk≤g(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.