2-D Dynamic Programming Knapsack
548. Coin Change
Medium 147 DSA Sheet
You are given an array coins of coin values and an integer amount. You have as many coins of each value as
you want.
Return the fewest coins that add up to exactly amount. If no mix of the coins adds up to amount, return
-1.
Example 1
Input: coins = [1, 5, 6, 9], amount = 11
Output:
2Explanation: 5 + 6 = 11 uses two coins. Taking the largest coin first gives 9 + 1 + 1, which uses three.
Example 2
Input: coins = [4, 6], amount = 7
Output:
-1Explanation: Every sum of 4s and 6s is even, so no mix of them makes 7.
Example 3
Input: coins = [3], amount = 0
Output:
0Explanation: An amount of 0 needs no coins at all.
Check your understanding
Work out the answer for this input before you write any code.
coins = [1, 3, 4], amount = 6
Constraints
1 ≤ coins.length ≤ 1001 ≤ coins[i] ≤ 1090 ≤ amount ≤ 104
Clarifying questions
What you would ask an interviewer before writing any code.