29 lines
795 B
Kotlin
29 lines
795 B
Kotlin
class Solution {
|
|
fun coinChange(
|
|
coins: IntArray,
|
|
amount: Int,
|
|
): Int =
|
|
IntArray(amount + 1) { Int.MAX_VALUE }.let { dp ->
|
|
// base case
|
|
dp[0] = 0
|
|
|
|
// sort the coins
|
|
coins.sort()
|
|
|
|
// precompute
|
|
(1..amount).forEach { total ->
|
|
for (coin in coins) {
|
|
when {
|
|
total - coin < 0 -> break
|
|
dp[total - coin] != Int.MAX_VALUE -> dp[total] = minOf(dp[total], 1 + dp[total - coin])
|
|
}
|
|
}
|
|
}
|
|
|
|
// return the minimum count for the target
|
|
when {
|
|
dp[amount] == Int.MAX_VALUE -> -1
|
|
else -> dp[amount]
|
|
}
|
|
}
|
|
}
|