在上一篇中，经过深入分析，已经得出一个能够递归的形式化的结果，现在则准备给出一个具体实现。
结果回顾
前述结果如下：caseOfChange(amount, cashList) {
// base case
if (amount.isNegative()) { // 负数
return 0;
}
if (amount.isZero()) { // 0元
return 1;
}
if (cashList.containsOnlyOneCash()) { // 只有一种零钱时
if (amount.canBeChangedWith(cashList.getTheOnlyOneCash())) { // 能换时，即能整除
return 1;
} else {
return 0;
}
}
// recursive case
return caseOfChange(amount.subtractBy(cashList.getFirstCash()), cashList)
+ caseOfChange(amount, cashList.newCashListWithoutFirstCash());
}
其实已经大体 OK 了，基本就差确定一下类型就差不多了。
代码实现
下面将给出一个 Java 的实现。Java 是一种面向对象的语言，有强大的类型抽象机制，我们可以将上述形式化结果翻译成面向对象的实现。我不清楚大家平时喜欢面向什么编程，我反正是面向显示器编程，偶尔面向键盘一下。
面向对象的实现
上述结果基本上只是差了类型（type or class）没有确定。抽象数据类型（ADT：Abstract Data Type）
对一个类型（类）来说，是对行为（behavior）和属性（property）的一种抽象与封装。行为刻画了一个类的功能，是对外的主体部分；（在 Java 中，即对应成员方法（member method））属性则关系到内部的具体实现，通常应该对外隐藏。（在 Java 中，即对应成员变量（member field））
引入自定义类型
直接将 amount 视作 Amount 类型，cashList 则为 CashList 类型。再仔细推敲一下，cashList 中的 cash 其实也就是 amount，或者说 amount 其实也就是 cash。这会更好地与现实接轨。因此，可引入两种自定义类型 Cash 和 CashList：
public class Cash {
private int value;
public Cash(int value) {
this.value = value;
}
}
public class CashList {
private List<Cash> list = new ArrayList<Cash>();
public CashList(Cash ... cashes) {
// TODO ...
}
}
其实也就是分别对 Integer 以及 Array（或者说 ArrayList）的轻量封装，这样我们就能加入自定义的行为。
确定类型的行为（方法）
现在考虑行为，基本上，前述描述中已经基本刻画了两种类型的行为。比如，isNegative，isZero 是 Cash 类中的方法，containsOnlyOneCash 等则是 CashList 中的方法。严格地说，对 Cash 类而言，其实只要对外提供一个方法即可，这是外界唯一关心的方法：将前述伪代码拷贝到类定义中，稍加修改就可以让 IDE 为我们自动生成那些方法定义了。
public int getCountOfChanges(CashList list)至于 isZero 之类的，只是一些内部辅助实现，定为 private 即可。
public class Cash {
// ...
// 对外接口
public int getCountOfChanges(CashList list) { /*...*/ }
// 内部递归实现
private int caseOfChanges(Cash cash, CashList list) { /*...*/ }
private boolean isNegative() { /*...*/ }
private boolean isZero() { /*...*/ }
private boolean canBeChangedWith(Cash cash) { /*...*/ }
private Cash subtractBy(Cash cash) { /.../ }
}
public class CashList {
// ...
public boolean containsOnlyOneCash() { /.../ }
public Cash getTheOnlyOneCash() { /.../ }
public CashList newCashListWithoutFirstCash() { /.../ }
public Cash getFirstCash() { /.../ }
}
引入枚举 enum 类型
再考虑到 cash 的种类是有限的，直接就用 enum 枚举代替了，只提供有限几个实例（instance）。public enum Cash {
CASH_100(100), CASH_50(50), CASH_20(20), CASH_10(10), CASH_5(5), CASH_1(1);
private int value;
private Cash(int value) {
this.value = value;
}
// ...
}
这样客户端代码就无法 new 出形形色色的 Cash，只能用这里定义好的，我们也免去了检查输入合法性的麻烦。
泛化的零钱 GenericCash
Cash 变为 enum 后，由于递归演算涉及到了一些中间结果：比如求 coc(100, [20, 5, 1]) 时经约减会出现 coc(80, [20, 5, 1]) 之类的，显然 80 不是 enum 中的一员。为此，引入一个新的类型 GenericCash，
Java 中的范型称为 Generic type，这里用 generic 表示一般化的零钱，也即递归运算过程中才会出现的那些。也正好把 isZero 等方法也打包到它的内部去：
class GenericCash {
// ...
public int getCountOfChanges() {}
private int caseOfChanges(GenericCash genericCash, CashList list) {}
private boolean canBeChangedWith(Cash cash) {}
private boolean isNegative() {}
private GenericCash subtractBy(Cash cash) {}
private boolean isZero() {}
}
这样，Cash 类就显得很简洁了。
局部内部类（local inner class）
考虑到只是在方法内部才会用到 GenericCash，外部根本不需要知道这个类的存在，直接把它扔在方法内部定义，public enum Cash {
// ...
// 对外接口
public int getCountOfChanges(final CashList list) {
// 方法内部类
class GenericCash {
// ...
}
return new GenericCash().getCountOfChanges();
}
}
这样，即便是 Cash 类中的其它地方也不知道这个类的存在。（也无需知道）
最终结果
一个完整的结果如下：Cash 类：
public enum Cash {
CASH_100(100), CASH_50(50), CASH_20(20), CASH_10(10), CASH_5(5), CASH_1(1);
private int value;
private Cash(int value) {
this.value = value;
}
// ================ 第二种方式，更加对象化，把第一种方式中的int类型的genericCash包装成类
public int getCountOfChanges(final CashList list) {
/**
* 一般化的现金值，在运算中，我们会逐步分割要换的零钱，这会导致出现一些中间值
* 举个例子，把100换成[20, 10, 5]，在运算中将出现把100分成80+20的情况，然后将计算把“80”换成[20,10,5]的情况
* 这里的80就是一般化的现金值，在实际中不会存在，但在我们的运算中会有意义。
*
* 这是一个方法内部类，仅仅只用于也只能用于这个方法中。
*
*/
class GenericCash {
private int value;
private GenericCash() {
// 由于是内部类，可以直接引用所在类的私有成员变量
value = Cash.this.value;
}
// 供递归调用时使用的构造函数
private GenericCash(int value) {
this.value = value;
}
private boolean canBeChangedWith(Cash cash) {
// 由于是内部类，可以直接引用cash的私有成员变量
return value % cash.value == 0;
}
private boolean isNegative() {
return value < 0;
}
private GenericCash subtractBy(Cash cash) {
return new GenericCash(value - cash.value);
}
private boolean isZero() {
return value == 0;
}
private int getCountOfChanges() {
// 由于是内部类，这里直接引用外围方法的list变量，这也是它为何要设置成final的原因
return caseOfChanges(this, list);
}
private int caseOfChanges(GenericCash genericCash, CashList list) {
if (genericCash.isNegative()) {
return 0;
}
if (genericCash.isZero()) {
return 1;
}
if (list.containsOnlyOneCash()) {
return genericCash.canBeChangedWith(list.getTheOnlyOneCash()) ? 1 : 0;
}
return caseOfChanges(genericCash.subtractBy(list.getFirstCash()), list)
+ caseOfChanges(genericCash, list.newCashListWithoutFirstCash());
}
}
// 由于内部类的关系，在这里完全不用向里面传递任何参数
return new GenericCash().getCountOfChanges();
}
}
CashList 类
public class CashList {
private List<Cash> list = new ArrayList<Cash>();
public CashList(Cash ... cashes) {
if (cashes == null || cashes.length == 0) {
throw new IllegalArgumentException("请传入至少一个参数！");
}
List<Cash> cashList = Arrays.asList(cashes);
for (Cash cash : cashList) {
if (!list.contains(cash)) {
list.add(cash);
} else {
throw new IllegalArgumentException("重复的参数！" + cash);
}
}
}
public boolean containsOnlyOneCash() {
return list.size() == 1;
}
public Cash getTheOnlyOneCash() {
return list.get(0);
}
/**
* 获取不带第一个元素的新list
* 如果当前是[20, 10, 5, 1]，那么将得到[10, 5, 1]
* @return
*/
public CashList newCashListWithoutFirstCash() {
List<Cash> dest = new ArrayList<Cash>(list);
dest.remove(0);
// new Cash[0] 只是为能推导出泛型类型，本身并无其它意义
//也可以使用强制类型转换： new CashSet((Cash[]) dest.toArray());
return new CashList(dest.toArray(new Cash[0]));
}
public Cash getFirstCash() {
return list.get(0);
}
}
面向过程的实现
当然，如果觉得对于这个不大的问题，面向对象方式显得笨重低效，可以简单给出一个较为过程式的实现，比如直接使用 int 和 array，也不需要对象了，直接就是 static 的方法。public static int caseOfChanges(int cash, int[] cashes) {
if (cash < 0) {
return 0;
}
if (cash == 0) {
return 1;
}
if (cashes.length == 1) {
return cash % cashes[0] == 0 ? 1 : 0;
}
// 递归调用
return caseOfChanges(cash - cashes[0], cashes)
+ caseOfChanges(cash, Arrays.copyOfRange(cashes, 1, cashes.length));
}
比起对象式的实现，这个显得简洁多了。（当然，考虑到健壮性，还需要多做些检查才行。）另：这里还是进行了数组的复制，如果能再引入一个 index 参数，则可以避免复制数组。
测试
以下是一些测试，把 100 元换成 50，20，10，5，1 元总共有 343 种不同结果：// ========== 对象式实现的测试
@Test
public void testGetCountOfChanges() {
CashList list = new CashList(CASH_1, CASH_5);
assertThat(CASH_10.getCountOfChanges(list)).isEqualTo(3);
}
@Test
public void testManyCountNoOrder() {
// 顺序并不重要
CashList list = new CashList(CASH_10, CASH_5, CASH_20, CASH_1, CASH_50);
assertThat(CASH_100.getCountOfChanges(list)).isEqualTo(343);
}
// ========== 过程式，静态式实现的测试
@Test
public void testZeroCountStaticWay() {
assertThat(Cash.caseOfChanges(50, new int[] {20})).isEqualTo(0);
}
@Test
public void testOneCountStaticWay() {
assertThat(Cash.caseOfChanges(100, new int[] {20})).isEqualTo(1);
}
@Test
public void testManyCountStaticWay() {
assertThat(Cash.caseOfChanges(100, new int[] {50, 20, 10, 5, 1})).isEqualTo(343);
}
注：零钱的顺序其实并不会影响最终结果。