Unbounded knapsack

Why it matters

Payment systems, stock cutting, and resource packaging often combine reusable sizes to reach an exact total at minimum cost. Choosing the largest option first can be wrong for ordinary denominations, while trying every sequence repeats the same remaining totals. The result must guarantee the fewest coins for any denominations and return −1 when the amount is unreachable.

You have unlimited coins of each value in coins. Return the fewest coins that sum to amount, or -1 if it is impossible.

Input

coins = [1, 3, 4], amount = 6

Output

2

For coins [1, 3, 4] and amount 6, brute recursion solves remainders such as 3 repeatedly, while greedy chooses 4 + 1 + 1. Fill dp[0] through dp[6] once; dp[3] = 1 makes dp[6] = 2 via 3 + 3.

For coins [1, 3, 4], set dp[0] = 0 and fill amounts upward. dp[1] = 1, dp[2] = 2, dp[3] = 1 using coin 3, and dp[4] = 1 using coin 4.

For amount 6, ending with 1 reads dp[5] + 1 = 3; ending with 3 reads dp[3] + 1 = 2; ending with 4 reads dp[2] + 1 = 3. Keep 2, representing 3 + 3. Infinity stays in any cell that no fitted coin can reach.