11.08.2023
518. Coin Change II medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/305
Problem TLDR
Ways to make amount
with array of coins
Intuition
This is a classical Dynamic Programming problem: the result is only depending on inputs – coins
subarray and the amount
, so can be cached.
In a Depth-First search manner, consider possibilities of taking
a coin and skipping
to the next.
Approach
HashMap gives TLE, but an Array cache will pass
Complexity
Time complexity:
O(nm)Space complexity:
O(nm)
Code
fun change(amount: Int, coins: IntArray): Int {
val cache = Array(coins.size) { IntArray(amount + 1) { -1 } }
fun dfs(curr: Int, left: Int): Int = if (left == 0) 1
else if (left < 0 || curr == coins.size) 0
else cache[curr][left].takeIf { it >= 0 } ?: {
dfs(curr, left - coins[curr]) + dfs(curr + 1, left)
}().also { cache[curr][left] = it }
return dfs(0, amount)
}