关于换零钱问题

换零钱问题

我们有一些50美分，25美分，10美分，5美分和一美分的硬币，要把1美元换成零钱，一共有多少种不同的方式？

关于递归的解决思路

对于这个问题，我们可以用递归的方式解决。
把总数为a的现金换成n种硬币的不同方式的数目等于：现金a换成除去第一种硬币之外的所有其他硬币的不同方式数目，加上现金a - d换成所有种类硬币的不同方式数目，其中d是第一种硬币的币值

这乍一看很抽象，实际上很好理解。
我们可以把硬币兑换的结果进行分类，以最初的换零钱问题为例：把一美元进行兑换，实际上可以分为两种结果。

1. 使用了50美分硬币进行兑换的
2. 没有使用50美分进行兑换的
   即，第一组都用了50美分的硬币，第二组都没有用50美分的硬币

这是可以不断递归的，我们可以在都用了50美分硬币的基础上继续分类，使用了50美分的分类方法中，可以有都使用了25美分的一组，可以有都没有使用25美分的一组。

因此，我们可以得到这样的算法：
. 如果a就是0，应该算作有1种换零钱的方式。
. 如果a小于0，应该算作有0种换零钱的方式。
. 如果n是0，应该算作0种换零钱的方式。

如果这种说法不太好理解，接下来可以通过代码对这段话进行理解。

关于构造函数抽象

我们将通过构造函数的方式解决这个问题。
构造函数有以下优点：

1. 可以将程序拆分成各个组成部分。这有利于维护程序和扩展程序。
2. 有利于通过构造函数解决一般性问题，而不是单一问题。

关于第二点，我们可以将最开始的换零钱问题进行延伸，我们可以提出这样的问题：

给了任意数量的美金，我们能写出一个程序，计算出所有换零钱方式的数目吗？

同样，我们将通过代码来理解这一点。

程序

因此我们可以得到初步的程序如下：
（函数 first_denomination 可以用硬币的种类数作为输入，返回第一种硬币的币值。在这里我们认为硬币按从小到大的顺序排列，实际上，无论硬币按什么顺序排列，都对我们递归的结果没有任何影响）

function count_change(amount) {
    return cc(amount,5);
}
function cc(amount, kinds_of_coins) {
    return amount === 0
           ? 1
           : amount < 0 || kinds_of_coins === 0
           ? 0
           : cc(amount,kinds_of_coins - 1)
             +
             cc(amount - first_denomination(kinds_of_coins),
		kinds_of_coins);
}
function first_denomination(kinds_of_coins) {
    return kinds_of_coins === 1 ? 1
         : kinds_of_coins === 2 ? 5
         : kinds_of_coins === 3 ? 10
         : kinds_of_coins === 4 ? 25
         : kinds_of_coins === 5 ? 50
         : 0;
}

1美元换硬币的方法数目如下：

count_change(100);
292

可以看到，通过构造函数抽象的方式，我们可以做到将这个问题拆分成几个部分。

1. 不同美元换硬币的方式
2. 统计硬币的种类数
3. 返回硬币的币值

同时，我们尽可能的将这个问题一般化了，我们当然可以使用count_change(200)来计算2美元换硬bf币的不同方法的数目。

关于递归与迭代

当然，仅仅如此，这段程序也并不完善。因为它产生的是树形递归的计算过程。
对于比较树形递归和线性迭代，我们可以以斐波那契数列为例。

以斐波那契数列为例

在斐波那契数列中，这一序列的每个数都是前两个数之和。
0，1，1，2，3，5，8，12，21

斐波那契数列的树形递归

显然，将这个定义写成递归函数并不难：

function fib(n) {
    return n === 0
           ? 0
           : n === 1
           ? 1
           : fib(n - 1) + fib (n - 2);
}

假设我们现在要计算fib(5),我们需要计算fib(4)和fib(3)。但是，为了计算fib(4),我们又需要计算fib(3)和fib(2)。
这一计算过程就像一棵树，也就是所谓树形递归。如图：

通过上图，我们可以发现，为了计算fib(5)，我们计算了两次fib(3)，这几乎占到了所有工作的一半。而我们计算fib(n)时，n越大，则进行的重复计算越多。

斐波那契数列的线性迭代

再让我们看另一段程序：

function fib(n) {
    return fib_iter(1, 0, n);
}
function fib_iter(a, b, count) {
    return count === 0
           ? b
	   : fib_iter(a + b, a, count - 1)
}

可以看到，这就是所谓的线性迭代。我们有下面的迭代过程：
a => a + b
b => a
在这个函数中，我们同样使用了递归的方式，但不同的是，其计算过程是线性的。这很好理解，因为当我们可以发现，计算fib(5)时，不再需要重复计算fib(3)了。

因此，线性迭代的效率要更高。

关于换零钱问题的线性迭代

我们已经有了换零钱问题的树形递归计算法，那么，不妨思考下，我们可以有换零钱问题的迭代方法吗？

与斐波那契数列不同的是，我们无法仅仅使用两个变量完成迭代。换零钱问题的线性迭代更具有难度。让我们看这段程序：

function count_change(total_amount) {
    const denominations = [1, 5, 10, 25, 50]; 
    const dp = new Array(total_amount + 1).fill(0);
    dp[0] = 1; 
    for (const coin_value of denominations) {。
        for (let amount = coin_value; amount <= total_amount; amount++) {
            dp[amount] += dp[amount - coin_value];
        }
    }
    return dp[total_amount];
}

可以看到，我们使用了名为dp的数据结构记录了不同总额换零钱的全部方法。
我们创建了dp变量，其中dp共有total_amount + 1项，且每一项为0，表示最开始无论何种总额，都只有0种兑换方式。因为我们要考虑0的存在，dp[0] = 1：凑出金额0只有1种方式（即不使用任何硬币）。
对于每一种硬币面额，我们遍历所有可能的金额amount，其中，最为关键的是：

dp[amount] += dp[amount - coin_value];

理解：当我们在考虑使用硬币coin_value时，凑出金额amount的新方法数量，等于不使用硬币coin_value时凑出amount的原有方法数dp[amount]加上使用至少一个硬币coin_value的方法数dp[amount - coin_value]。

循环结束后,dp[total_amount]即为最终答案。

这种计算结果效率无疑高了很多。

这样的算法思路被称为动态规划。

总结

1. 比起树形递归，线性迭代的效率要高得多
2. 我们可以用动态规划的思考方式，写出线性迭代的程序

题外话

其实除了动态规划外，还存在别的方式实现线性迭代的计算过程，但这里不作赘述。（因为效率比动态规划要低，不过仍然是值得了解的方式）

参考：

1. 1.2.2 Tree Recursion
2. Count the coins