如何计算硬币问题的可能组合

您可以使用生成函数方法来给出使用复数的快速算法。

给定硬币值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，这可能比枚举所有可能的组合要快。

希望有帮助。