Coin Change
Medium · 1-D Dynamic Programming
You are given a list of coin denominations and a target amount of money. Assuming you have an unlimited supply of each denomination, return the smallest number of coins needed to make up exactly that amount. If the amount cannot be formed exactly with the given denominations, return -1.
Examples
Input: coins = [1, 2, 5], amount = 11
Output: 3
Why: 11 can be made with 5 + 5 + 1, which uses only three coins, fewer than any other combination.Input: coins = [2], amount = 3
Output: -1
Why: Only even totals can be formed from coin value 2, so 3 is unreachable.Input: coins = [1], amount = 0
Output: 0
Why: No coins are needed to reach a target of zero.Constraints
1 <= coins.length <= 12, 1 <= coins[i] <= 2^31 - 1, 0 <= amount <= 10^4
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Coin Change. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.