我写了一个递归函数硬币（变化）问题在Scala中。
我与实现突破的StackOverflowError，我想不通为什么它会发生。
Exception in thread "main" java.lang.StackOverflowError
at scala.collection.immutable.$colon$colon.tail(List.scala:358)
at scala.collection.immutable.$colon$colon.tail(List.scala:356)
at recfun.Main$.recurs$1(Main.scala:58) // repeat this line over and over
这是我的电话：
println(countChange(20, List(1,5,10)))
这是我的定义：
def countChange(money: Int, coins: List[Int]): Int = {
def recurs(money: Int, coins: List[Int], combos: Int): Int =
{
if (coins.isEmpty)
combos
else if (money==0)
combos + 1
else
recurs(money,coins.tail,combos+1) + recurs(money-coins.head,coins,combos+1)
}
recurs(money, coins, 0)
}
编辑：我只是说在搭配的else if语句：
else if(money<0)
combos
它摆脱了错误的，但我的输出是1500的东西:(什么是错我的逻辑是什么？
Answer 1:
这是基于你的代码正确的解决方案：
def countChange(money: Int, coins: List[Int]): Int = {
def recurs(m: Int, cs: List[Int], cnt: Int): Int =
if(m < 0) cnt //Not a change, keep cnt
else if(cs.isEmpty) {
if(m == 0) cnt + 1 else cnt // plus cnt if find a change
}
else recurs(m, cs.tail, cnt) + recurs(m-cs.head, cs, cnt)
recurs(money, coins, 0)
}
无论如何，有一个简短的解决方案（但效率不高，你可以缓存中间的结果，使之有效。）
def countChange(m: Int, cs: List[Int]): Int = cs match {
case Nil => if(m == 0) 1 else 0
case c::rs => (0 to m/c) map (k => countChange(m-k*c,rs)) sum
}
Answer 2:
在第一个解决方案公认的答案有一个多余的最后一个参数由Paaro指出的 ，所以我想摆脱它。 第二个解决方案使用map ，我想避免，因为它不是在我假设你正在做的第1周或斯卡拉过程中尚未涉及。 此外，第二解决方案，理所当然地对笔者注意到，就这样慢，除非它使用了一些记忆化。 最后， Paaro的解决方案似乎有一个不必要的嵌套函数。
因此，这里是我结束了：
def countChange(money: Int, coins: List[Int]): Int =
if (money < 0)
0
else if (coins.isEmpty)
if (money == 0) 1 else 0
else
countChange(money, coins.tail) + countChange(money - coins.head, coins)
没有必要对大括号在这里，你可以看到。
我不知道是否可以进一步简化。
Answer 3:
该解决方案@Eastsun是好的，但是当金钱= 0，由于它返回1，而不是0失败，但你可以很容易地解决这个问题：
def countChange(money: Int, coins: List[Int]): Int = {
def recurs(m: Int, cs: List[Int], cnt: Int): Int =
if(m < 0) cnt //Not a change, keep cnt
else if(cs.isEmpty) {
if(m == 0) cnt + 1 else cnt // plus cnt if find a change
}
else recurs(m, cs.tail, cnt) + recurs(m-cs.head, cs, cnt)
if(money>0) recurs(money, coins, 0) else 0
}
Answer 4:
人们可以省略CNT参数，这一点，事实上，从来没有积累。 的复发函数总是返回0或1，因此优化算法将是：
def countChange(money: Int, coins: List[Int]): Int = {
def recurs(m: Int, cs: List[Int]): Int =
if(m < 0) 0 //Not a change, return 0
else if(cs.isEmpty) {
if(m == 0) 1 else 0 // 1 if change found, otherwise 0
}
else recurs(m, cs.tail) + recurs(m-cs.head, cs)
if(money>0) recurs(money, coins) else 0
}
Answer 5:
这里是一个DP方法，以减少在递归方法很多重新计算
object DP {
implicit val possibleCoins = List(1, 5, 10, 25, 100)
import collection.mutable.Map
def countChange(amount: Int)(implicit possibleCoins: List[Int]) = {
val min = Map((1 to amount).map (_->Int.MaxValue): _*)
min(0) = 0
for {
i <- 1 to amount
coin <- possibleCoins
if coin <= i && min(i - coin) + 1 < min(i)
} min(i) = min(i-coin) + 1
min(amount)
}
def main(args: Array[String]) = println(countChange(97))
}
看到从新手DP到先进的算法
Answer 6:
从理念https://github.com/pathikrit/scalgos/blob/9e99f73b4241f42cc40a1fd890e72dbeda2df54f/src/main/scala/com/github/pathikrit/scalgos/DynamicProgramming.scala#L44
case class Memo[K,I,O](f: I => O)(implicit i2k:I=>K ) extends (I => O) {
import scala.collection.mutable.{Map => Dict}
val cache = Dict.empty[K, O]
override def apply(x: I) = cache getOrElseUpdate (x, f(x))
}
def coinchange(s: List[Int], t: Int) = {
type DP = Memo[ (Int, Int), (List[Int], Int),Seq[Seq[Int]]]
implicit def encode(key: (List[Int], Int)):(Int,Int) = (key._1.length, key._2)
lazy val f: DP = Memo {
case (Nil, 0) => Seq(Nil)
case (Nil, _) => Nil
case (_, x) if x< 0 => Nil
case (a :: as, x) => f(a::as, x - a).map(_ :+ a) ++ f(as, x)
}
f(s, t)
}
文章来源: StackOverflowError for coin change in Scala?
