2-D Dynamic Programming Knapsack
549. Coin Change II
You are given an integer amount and an array coins of distinct coin values. You have as many coins of each
value as you want.
Return the number of different mixes of coins that add up to exactly amount. A mix is how many coins of each
value you use, so the order of the coins does not matter: 2 + 3 and 3 + 2 are the same mix. An amount of 0 has
exactly one mix, the one with no coins.
The number can be very large, so return it modulo 109 + 7.
Example 1
Input: amount = 10, coins = [2, 3, 5]
4Explanation: The mixes are 5 + 5, 5 + 3 + 2, 3 + 3 + 2 + 2 and 2 + 2 + 2 + 2 + 2.
Example 2
Input: amount = 12, coins = [5, 10]
0Explanation: Every mix of 5s and 10s adds up to a multiple of 5, and 12 is not one.
Example 3
Input: amount = 0, coins = [7]
1Explanation: The only mix is the one with no coins.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
0 ≤ amount ≤ 1041 ≤ coins.length ≤ 1001 ≤ coins[i] ≤ 109- All the values in
coinsare distinct.
Clarifying questions
What you would ask an interviewer before writing any code.