Untitled

mail@pastecode.io avatar
unknown
kotlin
2 years ago
657 B
0
Indexable
Never
import kotlin.math.max
import kotlin.math.min
import kotlin.collections.HashSet

class Solution {
    fun coinChange(coins: IntArray, amount: Int): Int {
        val memoized = mutableMapOf<Int, Int>() // Instead of memoized functions
        fun calc(source: Int): Int = memoized.getOrPut(source) {
            if (source == 0)
                0
            else if (source < 0)
                -1
            else
                coins
                    .reversed()
                    .map { calc(source = source - it) + 1 }
                    .filter { it > 0 }
                    .min() ?: -1
        }

        return calc(source = amount)
    }
}