您可以使用生成函数方法来给出使用复数的快速算法。
给定硬币值c1，c2，..，ck，以获得求和n的方法数量，您需要的是x的系数
(1 + x^c1 + x^(2c1) + x^(3c1) + ...)(1+x^c2 + x^(2c2) + x^(3c2) + ...)....(1+x^ck + x^(2ck) + x^(3ck) + ...)
这与在中找到x ^ n的系数相同
1/(1-x^c1) * 1/(1-x^c2) * ... * (1-x^ck)
现在使用复数，x ^ a-1 =（x-w1）（x-w2）…（x-wa）其中w1，w2等是单位的复数根。
所以
1/(1-x^c1) * 1/(1-x^c2) * ... * (1-x^ck)
可以写成
1/(x-a1)(x-a2)....(x-am)
可以使用部分分数重写的是
A1/(x-a1) + A2/(x-a2) + ... + Am/(x-am)
可以很容易地找到x ^ n的系数：
A1/(a1)^(n+1) + A2/(a2)^(n+1) + ...+ Am/(am)^(n+1).
计算机程序应该很容易就能找到Ai和ai（可能是复数）。当然，这可能涉及浮点计算。
对于较大的n，这可能比枚举所有可能的组合要快。
希望有帮助。
