钱币兑换问题

钱币兑换问题：

仅有 n 种指定面值的硬币(c1, c2, c3, …, cn), 将钱 N 兑换成 这些面值的硬币，总共有多少种兑换方法？

递推

最简单的递推的想法: 枚举每种货币的使用次数，当使用 k 次第 n 种硬币凑出了 j 钱数的方案，应当等于只使用了前 n-1 种硬币凑出了 dp[j-k*coin[n]] 钱数，而凑出钱数 money 的总方案，应当等于仅使用了 前 1 中硬币、仅使用的前 2 种硬币、…、仅使用了前 n-1 中硬币、使用了全部n种硬币的方案的总和。暗按照这个想法，直接递推求解即可。

int dp[MAX_N] = {0};

int exchange(int money, int n, int coin[]) {
    dp[0] = 1;
    for(int i = 1; i <= n; ++i) {
        for(int j = money; j >= coin[i]; --j) {
            for(int k = j / coin[i]; k > 0; --k) {
                dp[j] += dp[j - k*coin[i]];
            }
        }
    }
    return dp[money];
}

这个方法还可以进一步简化。在上面的方法中，我们从大往小地枚举钱数，考虑到每种硬币都有无限枚可以选，因此，在选择第 i 中硬币时，我们只需要从一个绝无已经选择第 i 种硬币的可能的情形 开始枚举递推即可。在具体实现上，只要改变总钱数 j 的递推顺序即可。进一步地，采用压缩空间的写法，代码如下：

int dp[MAX_N] = {0};

int exchange(int money, int n, int coin[])
{
    dp[0] = 1;
    for(int i = 1; i <= n; ++i) {
        for(int j = coin[i]; j <= money; ++j) {
            dp[j] += dp[j-coin[i]];
        }
    }
    return dp[money];
}

这种方法与求解完全背包的算法的思路有很大的相似之处。

母函数

钱币兑换问题本质上是一个组合问题：以 n 中硬币来组合出制定的钱数。因此，也可以通过母函数的方法来求解钱币组合问题。

\[\begin{aligned} f(n) &= (1+x+x^{c_1}+x^{2c_1}+\dots) \\ &\times (1+x+x^{c_2}+x^{2c_2}+\dots) \\ &\times \dots \\ &\times (1+x+x^{c_n}+x^{2c_m}+\dots) \end{aligned}\]

所要求的兑换方案数，即第 $n$ 项的系数，接下来，模拟多项式展开即可。