Given a set of coin denominations and a target amount, return the fewest coins that make it exactly. Why would you not just take the largest coin first each time?

Why largest-first fails, on 1, 3 and 4

Deal with the greedy question first, because it is the part with a right answer that most candidates only gesture at. Take denominations 1, 3 and 4, and a target of 6. Largest-first takes a 4, then cannot take another, so it takes a 1 and a 1: three coins. The optimum is 3 and 3: two coins. The greedy answer is wrong by one coin on a six-unit target with three denominations, which is about as small a counterexample as exists.

What matters is not that you know a counterexample but that you can construct one on the spot, because that is the difference between having memorised that greedy fails and understanding why. Greedy works when taking the largest coin never removes an option you needed, and it stops working as soon as a smaller denomination divides the remainder more cleanly than the largest one does. British and euro coin sets happen to be canonical, meaning greedy is optimal on them, and that is exactly why the failure is counterintuitive to anyone reasoning from the coins in their pocket.

Note that greedy is not merely suboptimal here, it can also fail to find any answer at all. With denominations 4 and 3 and a target of 6, largest-first takes a 4 and then cannot reach 6, so a greedy implementation that never backtracks reports impossible for an amount that is reachable as 3 plus 3.

The state, and why one dimension is enough

Define best[i] as the fewest coins that sum to exactly i. That is the whole state, and it is one dimensional because nothing about how you reached amount i constrains what you may do next: coins are unlimited and order does not matter, so the remaining subproblem depends on the remaining amount alone.

The recurrence follows directly. For each denomination c not exceeding i, one way to make i is a single c on top of an optimal solution for i minus c, so best[i] is one plus the smallest best[i - c] over all such c. best[0] is 0, which is the base case that makes the whole thing work: making nothing takes no coins.

The sentinel that must not be the maximum integer

Amounts that no combination reaches must be representable, and the natural instinct is to initialise the table with the largest integer the type holds. That is a bug, because the recurrence adds one to whatever it finds, and adding one to the maximum integer wraps round to the minimum. An unreachable subproblem then looks like the cheapest option available, and the table fills with negative nonsense that propagates upwards.

Choose a sentinel that is larger than any real answer but small enough to increment safely. The amount plus one is ideal: no solution can use more than amount coins, since the smallest possible denomination is 1, so any entry still holding amount + 1 at the end is genuinely unreachable.

int fewestCoins(int[] coins, int amount) {
    int impossible = amount + 1;               // bigger than any real answer, safe to add 1 to
    int[] best = new int[amount + 1];
    Arrays.fill(best, impossible);
    best[0] = 0;

    for (int target = 1; target <= amount; target++) {
        for (int coin : coins) {
            if (coin <= target && best[target - coin] + 1 < best[target]) {
                best[target] = best[target - coin] + 1;
            }
        }
    }
    return best[amount] == impossible ? -1 : best[amount];
}

Filling order, and the one place it matters

In this version the outer loop is over amounts and the inner over denominations, and swapping them changes nothing: every best[target - coin] is complete before best[target] is read either way, because target - coin is strictly smaller than target. Candidates often assume loop order is always load-bearing in coin problems, and here it is not.

It becomes load-bearing the moment the objective changes. If you are counting the number of distinct combinations rather than minimising coins, the denomination loop must be outside: with amounts outside, you count 1 then 3 and 3 then 1 as two different results and end up counting ordered sequences instead of combinations. And if each coin may be used at most once, the inner amount loop must run downwards so that a coin is not reused within its own pass. Being able to state which of the three variants you are solving, and which loop discipline that variant demands, is the signal separating a candidate who has understood the table from one who has memorised one of its three shapes.

Cost, and when the table is the wrong answer

Time is O of the amount times the number of denominations, and space is O of the amount. Both matter: quoting only the amount hides the fact that a currency with hundreds of denominations is a different problem from one with four.

The important consequence is that this is pseudo-polynomial. The cost scales with the numeric value of the amount, not with the number of digits used to write it, so a target of a billion means a billion table entries regardless of how few denominations there are. At that point the table is the wrong tool and the answer lies in number theory over the specific denominations rather than in dynamic programming. Saying so unprompted is worth more than any optimisation of the loop.