Given coin denominations and an amount, return the fewest coins to make that amount, or -1 if impossible.
Defining the DP state and transition; why greedy fails for arbitrary coins.
dp[a] = fewest coins to make amount a. For each amount, try every coin: dp[a] = min(dp[a], dp[a−coin] + 1). Build up from 0. Greedy (biggest coin first) is wrong for coin sets like [1,3,4] making 6 — DP is the safe answer. State + transition + base case (dp[0]=0). Initialize the rest to Infinity so unreachable amounts stay unreachable and never masquerade as a real solution; the final Infinity check maps to -1. This is the 'unbounded knapsack' shape — each coin is reusable — so the inner loop iterates coins for every amount, unlike the 0/1 knapsack where each item is used at most once.
Min/max to reach a target from smaller sub-targets, when greedy can be fooled → bottom-up DP.
Time O(amount·coins) · Space O(amount)