322. Coin Change

Practice Coin Change for free on NudgeCode: Medium, Dynamic Programming pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

You have unlimited coins of each value in coins. Return the fewest coins that add up to exactly amount, or -1 if it cannot be done.

Example

coins = [1,2,5], amount = 11  ->  3    (5 + 5 + 1)
coins = [2],     amount = 3   ->  -1

Constraints

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4