'Kotlin Coin Change recursive functional approach
I'm trying to solve leetcode problem with next basic idea:
fun coinChange(coins: IntArray, amount: Int): Int {
fun calc(source: Long, lvl: Int): Int =
if (source == amount.toLong())
lvl
else if (source > amount)
-1
else
coins
.map { calc(source = source + it, lvl = lvl + 1) }
.filter { it > 0 }
.sorted()
.firstOrNull() ?: -1
return calc(source = 0, lvl = 0)
}
This algorithm looks correct, but it is very slow and fails the tests because of stack overflow. In that case I'm tried to speed up it a little bit, but now it's not working correctly:
fun coinChange(coins: IntArray, amount: Int): Int {
val memoized = mutableMapOf<Int, Int>()
fun calc(source: Int, lvl: Int): Int =
if (source == amount)
lvl
else if (source > amount)
-1
else
memoized.getOrElse(source) {
val evaluated = coins
.reversed()
.map { calc(source = source + it, lvl = lvl + 1) }
.filter { it > 0 }
.minOrNull() ?: -1
memoized[source] = evaluated
evaluated
}
return calc(source = 0, lvl = 0)
}
For input coinChange(coins = intArrayOf(186, 419, 83, 408), amount = 6249) it's returns 36, but must be 20. Would you kindly help me?
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
