Hard · DP

Coin Change

You met this problem once already — with coins 25/10/5/1, where greedy was provably optimal. Change the denominations and that proof evaporates. The dynamic program does not care which coins it gets: it asks, for every sub-amount, the honest minimum.

At a glance<code>best[0] = 0</code>; for every amount x and coin c: <code>best[x] = min(best[x], best[x-c] + 1)</code>. Answer <code>best[amount]</code>, or -1 if it never became reachable.

Problem

Input: The first line has n and amount (1 ≤ n ≤ 10, 1 ≤ amount ≤ 10000). The second line has n distinct denominations (1 ≤ c ≤ 1000), unlimited supply of each.

Output: The fewest coins that sum to exactly amount, or -1 if it is impossible.

Samples:

Input	Output
`3 11 1 2 5`	`3`
`2 7 2 4`	`-1`

With coins {1, 3, 4} and amount 6, greedy takes 4+1+1 (three coins) but 3+3 takes two — run both on the sample coins and watch the difference. The table never picks the locally best coin; it picks the best ending.

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — Define the cell before writing the loop

best[x] means: the fewest coins that make exactly x, or infinity if x is unreachable. With that definition the recurrence is almost forced — the last coin of an optimal payment for x is some c, and before it there was an optimal payment for x − c: best[x] = min over c of best[x-c] + 1.

Hint 2 — Infinity needs a bodyguard

Use a large INF (say 1000000000) for unreachable amounts — but guard the transition: if (best[x-c] != INF && best[x-c] + 1 < best[x]). Without the guard, INF + 1 enters the table and the poison spreads to every larger amount. This single missing check is the most common bug in this problem.

Hint 3 — -1 is a table answer too

After the fill, best[amount] either holds a real count or is still INF — print -1 in the second case. Do not try to detect impossibility during the loop; the table is done when it is done, and impossibility is just a cell that never improved.

Solution (try it first!)

#include <iostream>
using namespace std;

int best[10005];

int main() {
    int n, amount;
    cin >> n >> amount;
    int c[10];
    for (int i = 0; i < n; i++) cin >> c[i];

    const int INF = 1000000000;
    best[0] = 0;
    for (int x = 1; x <= amount; x++) best[x] = INF;

    for (int x = 1; x <= amount; x++) {
        for (int i = 0; i < n; i++) {
            if (c[i] <= x && best[x - c[i]] != INF && best[x - c[i]] + 1 < best[x]) {
                best[x] = best[x - c[i]] + 1;
            }
        }
    }

    cout << (best[amount] == INF ? -1 : best[amount]) << endl;
    return 0;
}

This is the unbounded knapsack in its simplest costume, and the direct vindication of Minimum Coins — same story, one chapter later. The pattern to carry forward: when greedy has no proof, define a table over sub-problems and let transitions do the deciding. The same table with a second dimension will do 0/1 knapsack, then subsets, then everything.

Deep dive

Why this works

Greedy took the biggest coin and failed on {1,3,4} — so abandon local choices and define best[x] = fewest coins for exactly x. The last coin of any optimal payment is some c, so best[x] = min(best[x−c] + 1) over coins. Bottom-up over x means every sub-answer is ready when referenced: no proof of greedy needed, because nothing is greedy.

The cost

O(n × amount) time, O(amount) space — 10 × 10000 = 100,000 transitions, instant. The exponential alternative (try every coin at every step) recomputes the same sub-amounts astronomically many times.

Where it goes wrong

Letting INF+1 into the table: transition without the best[x-c] != INF guard and the poison spreads to every larger amount. This is the single most common bug.
Forgetting best[0] = 0 — the base case that makes 'pay exactly 0 with 0 coins' legal, from which all chains grow.
Printing 0 instead of -1 for impossible amounts, or testing impossibility inside the loop: the table is finished first, impossibility is just a cell still holding INF.

Next step

The greedy counterpart that works (and why) is Minimum Coins; the DP you wrote here is the unbounded knapsack in disguise. Add one dimension and it becomes 0/1 knapsack — the gateway to a whole family.

Two things to remember

When greedy has no proof, define a table over sub-amounts and let transitions decide.
INF is a sentinel, not a number: guard every transition that touches it.

🐞 This version fails — open it and try

Greedy again — takes 4+1+1 for amount 6 where 3+3 takes two

#include <iostream>
using namespace std;

int main() {
    int n, amount;
    cin >> n >> amount;
    int c[10];
    for (int i = 0; i < n; i++) cin >> c[i];
    int left = amount, count = 0;
    while (left > 0) {
        int take = -1;
        for (int i = 0; i < n; i++) {
            if (c[i] <= left && c[i] > take) take = c[i];  // bug: greedy
        }
        if (take == -1) { cout << -1 << endl; return 0; }
        left -= take;
        count++;
    }
    cout << count << endl;
    return 0;
}