The Art Gallery Guardian

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 d1,,dmd_1,\ldots,d_m and nn, and output {(c1,,cm)ciN,i=1mcidi=n}. \left|\{ (c_1,\ldots,c_m) | c_i\in \N , \sum_{i=1}^m c_i d_i = n\} \right|.

The dynamic programming solution can solve this problem in O(nm)O(nm) time and O(min(n,max(d1,,dm))O(\min(n,\max(d_1,\ldots,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)O(n) time, and it is no longer the fastest algorithm. Since if denominations are fixed, we can find the solution in O(1)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=1mj=0xjdi C(x) = \prod_{i=1}^m \sum_{j=0}^\infty x^{j d_i}

The coefficient for xnx^n is our solution. Let l=lcm(d1,,dm)l = \lcm(d_1,\ldots,d_m).

C(x)=i=1mj=0xjdi=i=1m(1xdi)1=(i=1mj=0l/di1xjdi)(1xl)m=(i=1mj=0l/di1xjdi)k=0(k+m1m1)xlk\begin{aligned} 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 { k+m-1 \choose m-1 } x^{lk}\\ \end{aligned}

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

This is of course easy as we only need to test kk’s where nlkdeg(P)n-lk \leq \deg(P). There are only constant number of them.

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

Posted by Chao Xu on .
Tags: enumerative combinatorics, math.