Prerequisite: Unbounded Knapsack Introduction
This is an unbounded knapsack problem: each coin denomination can be used unlimited times. We minimize coin count rather than count combinations.
You are given a list coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. Each coin can be used any number of times. If amount cannot be made up by any combination of the coins, return -1.
coins = [1, 2, 5], amount = 11
3
11 = 5 + 5 + 1 uses three coins, and no combination reaches 11 with two.
coins = [1, 3, 4], amount = 6
2
6 = 3 + 3 uses two coins. Repeatedly taking the largest coin that fits gives 4 + 1 + 1, three coins, so the greedy choice is not always optimal.
coins = [3], amount = 1
-1
No multiple of 3 equals 1, so the amount cannot be made at all.
1 <= coins.length <= 121 <= coins[i] <= 2^31 - 10 <= amount <= 10^4