Given coin denominations with unlimited supply and a target amount, the machine must return the minimum number of coins that sums to the target, or -1 when no combination exists. Every coin can be reused, which makes this an unbounded knapsack rather than a 0/1 problem.
The key insight is that the answer composes from smaller amounts: the fewest coins for amount a equals 1 plus the fewest coins for a - c, minimized over every coin c that fits. Because coins are unlimited, the machine must iterate amounts in ascending order so each subproblem is solved before any amount that depends on it.
The approach runs in three steps. First, initialize dp[0] = 0 and every other entry to infinity. Second, for each amount from 1 up to the target, try every coin and keep the minimum of dp[a - c] + 1. Third, return dp[target] if it is finite, otherwise -1. Time is O(amount x len(coins)) and space is O(amount).
The trickiest edge case is the unreachable amount: entries that no coin combination can reach stay at infinity, and the machine must map infinity to -1 at the end. A related trap is amount 0, which is always reachable with 0 coins and never an error.
def coinChange(coins, amount):
dp = [float("inf")] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] != float("inf") else -1