1382. Find Minimum Number of Coins for Each Amount

Given coin denominations available in unlimited supply, build a table answering every amount from 0 up to maxAmount: the fewest coins summing exactly to that amount, or -1 when the amount cannot be formed. Return the whole table as an array of length maxAmount + 1.

Input: A JSON object {"coins": [<denominations>], "maxAmount": <largest amount>}.

Output: Return the array of minimum coin counts for amounts 0 through maxAmount.

Examples

Input: {"coins":[1,2,5],"maxAmount":5}
Output: [0,1,1,2,2,1]
Explanation: The table of minimum coin counts is [0,1,1,2,2,1].

Input: {"coins":[2],"maxAmount":3}
Output: [0,-1,1,-1]
Explanation: Odd amounts are impossible -> [0,-1,1,-1].

Constraints

• 1 <= len(coins) <= 12
• 1 <= coins[i] <= 100
• 0 <= maxAmount <= 10^4

Asked by