Computing number of ways to make change

Question

Given a list $C=[c_1,c_2,\dots,c_k]$ of positive integers, representing the values of $k$ varieties of coins, and a positive integer $n$, let $f(n,C)$ be the number of handfuls of coins with total value $n$. The order within the handful does not matter, and there is an infinite supply of each variety of coin.

What is the state-of-the-art algorithm to compute $f(n,C)$?

Equivalently, $f(n,C)$ is the number of ways to choose non-negative integers $x_i$ so that $n=\sum_{i=1}^k x_ic_i$.

The list $C$ can have repeats, and the interpretation is that there are two varieties of coin with the same value. For example, $f(3,[2,1,1])=6$. Letting $A$ and $B$ be the coins of value $1$, and $C$ be the coin of value $2$, the $6$ possible handfuls are $$ (A,A,A),(A,A,B),(A,B,B),(B,B,B),(A,C),(B,C) $$

I can think of two solutions. Which is faster depends on $n$ and $C$.

• Dynamic programming: Let $C'$ denote $C$ with its last entry removed. A use-it-or-lose-it argument gives $$f(n,C) = f(n-c_k,C)+f(n,C') .$$ This lets you compute $f(n,C)$ by filling out an $n\times k$ DP table, which takes $$\boxed{\Theta(nk)}$$ additions and look-ups.

• Matrix exponentiation: I will illustrated in the case $C=[2,3,4]$. Letting $a_n=f(n,C)$, then $a_n$ satisfies the recurrence (see https://cs.stackexchange.com/a/87810/24590) $$ a_n = a_{n-2}+a_{n-3}+a_{n-4}-a_{n-5}-a_{n-6}-a_{n-7}+a_{n-9} $$ Any linear recurrence can be solved by computing the $n^{th}$ power of a certain matrix. In this case, the recurrence has order $c_1+\dots+c_k$, so this algorithm takes $$ \boxed{O(\log n \cdot M(c_1+\dots+c_k))} $$ arithmetic operations, where $M(k)$ is the number of arithmetic operations required when multiplying two $k\times k$ matrices (naively $M(k)=k^3$, state of the art is $k^{2.3728639}$). We get $\log n$ by using exponentiation by squaring.

The second algorithm is asymptotically much better as $n\to\infty$, but the first is better when the sum of $C$ is large.

Are there any known faster algorithms?

Answer 1

From a theoretical perspective, you can diagonalise (well, decompose to Jordan normal form) to do the matrix power. It costs $O(M(c_1+\dots+c_k))$ to decompose, $O(\log n \cdot (c_1+\dots+c_k))$ to raise the diagonal matrix to the $n$th power, and $O(M(c_1+\dots+c_k))$ to finish up.