StackOverflowError Scala中的硬币更改？

Question

我正在为Scala中的Coin (change) problem编写递归函数。

我的实现中断了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

的@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 3

可以省略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 4

第一种方案中the accepted answer有多余的最后一个参数as noted by Paaro所以我想摆脱它。第二个解决方案使用了map，我想避免它，因为它在第一周还没有被覆盖，或者我假设你正在使用Scala课程。另外，作者正确指出，第二种解决方案会慢一些，除非它使用一些记忆。最后，Paaro's solution似乎有一个不必要的嵌套函数。

因此，这里是我结束了：

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 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 from novice to advanced的算法