Deltamaster Tech Center

首先简单描述一下这个经典的找零问题：

已知需要找零的数量，以及可用的硬币面值，求用这些面值的硬币，有多少种方法拼凑出要求的找零数量。

比如要求找零4元，可用的硬币只有1元和2元两种面值，那么所有可能的方案是，[1, 1, 1, 1]、[1, 1, 2]、[2, 2]三种。（不同顺序不作为不同方案）

设计一个函数，接受两个参数：

• money：Int，表示需要拼凑的找零数量。
• coins：List[Int]，所有可用的硬币面值。

简单分析一下这个问题。直观地用递归的思路去考虑，所有可能的方案，就等于以下两部分之和：

• 用一枚某种面值的硬币x后，剩余找零数的找零方案数量；
• 用除了x以外的其他硬币的找零方案数量。

而递归终止条件就是，找零的数量小于或等于0，或者没有硬币可以用了。

  def countChange(money: Int, coins: List[Int]): Int = {
    if (money < 0) 0
    else coins match {
      case Nil => if (money == 0) 1 else 0
      case x::xs => countChange(money - x, coins) + countChange(money, xs)
    }
  }

这段代码用到了Scala的Pattern Matching。Nil是空List对象，继承自List，而x::xs则表示一个非空的List，其中x是用来匹配列表的head，而xs则是列表的tail，xs可以匹配任何List，当然也包括Nil。所以这两个case覆盖了所有的情形，要么为空，要么不为空，如果不为空，则将这个列表decompose成构造参数x和xs，供后面的表达式使用。