找零问题——Scala实现

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

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

比如要求找零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,供后面的表达式使用。