LeetCode: Coin Change Solution
Approach
Let recursion(i, amount)
be the minimums of coins of 0..i
sum up to amount
Base cases:
amount
is0
amount
is below0
or no coin left
Choices:
- Take the coin
- Skip the coin
1recursion(i, amount) = min(takeCoin(i, amount - valueOf(i)), skipCoin(i, amount))
Implementation
1var coinChange = function (coins, amount) {2 let memo = Array.from({ length: coins.length }, _ => Array(amount).fill(null))34 const recursion = (ithCoin, remainingAmount) => {5 if (remainingAmount === 0) return 06 if (remainingAmount < 0 || ithCoin < 0) return Infinity78 // query from cache9 if (memo[ithCoin][remainingAmount] != null)10 return memo[ithCoin][remainingAmount]1112 const takeCoin = 1 + recursion(ithCoin, remainingAmount - coins[ithCoin])13 const skipCoin = recursion(ithCoin - 1, remainingAmount)14 const res = Math.min(takeCoin, skipCoin)1516 // cache the result17 memo[ithCoin][remainingAmount] = res1819 return res20 }2122 const res = recursion(coins.length - 1, amount)2324 return res === Infinity ? -1 : res25}
References
Similar problems
Minimum Cost For Tickets
Maximum Value of K Coins From Piles
Minimum Number of Operations to Convert Time
Comments
Loading comments...
Tags
leetcode
dynamic programming
Apply and earn a $2,500 bonus once you're hired on your first job!
Clients from the Fortune 500 to Silicon Valley startups
Choose your own rate, get paid on time
From hourly, part-time, to full-time positions
Flexible remote working environment
A lot of open JavaScript jobs!!
Fact corner: Referred talent are 5x more likely to pass the Toptal screening process than the average applicant.
Still hesitate? Read HoningJS author's guide on dealing with Toptal interview process.