Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
object main
{
val coins = Array(1, 5, 10, 25)
val minCoin = coins.reduceLeft (_ min _)
var table: Map[Int, Seq[Int]] = Map()
val infinity: Seq[Int] = for (i <- 1 to 100000) yield i
def calculateMinCoins(n: Int): Seq[Int] = {
if (n == 0) { Seq() }
else if (n < minCoin) { infinity }
else {
table getOrElse (n, {
val subSolutions: Array[(Int, Seq[Int])] = coins map { c => (c, calculateMinCoins(n - c)) }
val bestSubsolution = (subSolutions.sortBy (_._2.length)).head
val solution = bestSubsolution._2 ++ Seq(bestSubsolution._1)
table = table.updated(n, solution)
solution
})
}
}
def main(args: Array[String]): Unit = {
println(calculateMinCoins(9))
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment