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 and , and output
The dynamic programming solution can solve this problem in time and space.
Is it efficient? It’s a very efficient pseudo-polynomial time algorithm.
However if we fixed the denominations, this runs in time, and it is no longer the fastest algorithm. Since if denominations are fixed, we can find the solution in 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.
The coefficient for is our solution. Let .
Now, notice the first part can be precomputed as some polynomial with finite degree. Let it be , then we get that we need to find the coefficient of in the following expression.
This is of course easy as we only need to test ’s where . There are only constant number of them.
Also notice those binomial coefficient need at most multiplications. Thus we can find the solution in time.