Fewest Coins for Amount

Problem Statement

You're given a set of coin denominations, each usable as many times as you like, and a target amount. Find the smallest number of coins that add up to exactly that amount. If there's no way to make the exact amount with these denominations, print -1 instead.

Input Format

The input has exactly two lines:

• Line 1: the coin denominations, as space-separated positive integers, no two of which are the same.
• Line 2: a single integer, the target amount.

Output Format

Print a single integer: the minimum number of coins that sum to exactly the target amount, or -1 if no combination of the given denominations reaches it exactly.

Example Walkthrough

Take the first sample: denominations 1 3 8, target 19. Imagine building up a table dp where dp[x] is the fewest coins needed to make amount x, starting from dp[0] = 0 (zero coins make an amount of 0). For each amount from 1 up to 19, dp[x] is the smallest of dp[x - c] + 1 over every coin c that's small enough to fit (c <= x): dp[1] = dp[0] + 1 = 1 (one 1-coin). dp[2] = dp[1] + 1 = 2 (two 1-coins — the only option, since 3 doesn't fit yet). dp[3] = 1 (one 3-coin, since dp[0] + 1 beats dp[2] + 1 = 3). dp[4] = 2 (a 3-coin and a 1-coin). dp[5] = 3 (3 + 1 + 1). dp[6] = 2 (two 3-coins, beating dp[5] + 1 = 4). dp[7] = 3 (3 + 3 + 1). dp[8] = 1 (one 8-coin, far better than dp[7] + 1 = 4 or dp[5] + 1 = 4). Continuing this way up to dp[19]: dp[11] = dp[8] + 1 = 2 (8 + 3), which ties dp[3] + 1 = 2 (3 + 8, the same two coins in the other order); dp[16] = dp[8] + 1 = 2 (two 8-coins); and finally dp[19] is the smallest of dp[18] + 1 = 5, dp[16] + 1 = 3, and dp[11] + 1 = 3, so dp[19] = 3 (two 8-coins and one 3-coin). No combination of 1s, 3s, and 8s reaches 19 in fewer than 3 coins, matching the expected output.

Approach

Trying combinations directly — for instance, recursively choosing a first coin and then solving the remaining amount — looks natural, but the same remaining amount can be reached by many different sequences of earlier choices, and a naive recursive solution ends up solving those repeated remaining amounts over and over. This is the same kind of repeated-subproblem issue that shows up when computing Fibonacci numbers by naive recursion, and it has the same fix: don't recompute an already-solved subproblem, build it up once and reuse it.

Build a table dp indexed by amount, from 0 up to the target. dp[0] = 0 by definition — no coins are needed to make nothing. For every larger amount x, dp[x] depends only on smaller amounts: for each coin c that's no larger than x, using one of that coin leaves amount x - c still to make, which costs dp[x - c] coins by definition (already computed, since x - c < x), plus the one coin just used. dp[x] is the smallest such value across every coin choice — try every coin, and keep the best. If no coin makes progress possible (every relevant dp[x - c] is itself unreachable), dp[x] stays unreachable too.

Filling the table from dp[0] up to dp[amount], in order, guarantees that whenever dp[x] is being computed, every dp[x - c] it depends on has already been finalized. Once the table is complete, dp[amount] is the answer directly — or, if it was never updated away from its "unreachable" placeholder, the amount can't be made exactly with these coins, so the answer is -1.

Common Mistakes

• Trying to solve this with a greedy approach — always picking the largest coin that fits. Greedy happens to work for denominations like 1, 5, 10, 25, but it isn't correct in general. With denominations 1, 3, and 4 and a target of 6, greedy would pick 4, then have to fill the remaining 2 with two 1-coins, for 3 coins total (4 + 1 + 1) — but 3 + 3 reaches 6 in only 2 coins. Only checking every combination systematically, as the dp table does, is guaranteed to find the true minimum.
• Not distinguishing "unreachable" from an actual coin count of 0. If the dp table is initialized with 0 everywhere instead of a placeholder like infinity, an amount that's genuinely impossible to make can end up looking like it costs 0 coins, and the final -1 check has no way to tell reachable amounts apart from unreachable ones.
• Forgetting the amount = 0 case. It's tempting to assume the answer must be at least 1, but making an amount of exactly 0 correctly takes 0 coins — this should fall out naturally from dp[0] = 0 rather than needing a special case, as long as the base case is set up correctly from the start.