Counting ways against fewest coins

Two questions about the same coins, with recurrences that differ by one loop order and answer very different things.

Fewest coins

def min_coins(coins, amount):
    best = [float('inf')] * (amount + 1)
    best[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != float('inf') else -1

Infinity is the base fill, not zero, because an unreachable amount must not look free. Returning -1 for unreachable is the usual contract and has to be handled explicitly.

Counting combinations

def count_ways(coins, amount):
    ways = [0] * (amount + 1)
    ways[0] = 1                        # one way to make nothing
    for c in coins:                    # coins OUTSIDE
        for a in range(c, amount + 1):
            ways[a] += ways[a - c]
    return ways[amount]

The loop order is the whole answer. Coins outside means each coin is considered once for the whole table, so a combination is built in a fixed coin order and counted once.

Swap the loops:

for a in range(1, amount + 1):
    for c in coins:
        ways[a] += ways[a - c]         # counts PERMUTATIONS

Now 1+2 and 2+1 are counted separately. For amount 3 with coins 1 and 2, the first gives 2 and the second gives 3.

Neither is wrong. They answer different questions, and reading which one the problem asked is the skill.

Why greedy fails

Coins 1, 10, 25 and an amount of 30. Greedy takes 25, then five 1s: six coins. The optimal is three 10s.

Greedy works on the usual Indian and American systems, which is exactly the danger: every example you try casually succeeds, and it fails on a denomination set you were not given. An interviewer asking "why not greedy" wants the counterexample, not a general statement about greedy algorithms.

Reconstructing which coins

The tables hold counts and minimums. To report the actual coins, walk back:

a, chosen = amount, []
while a > 0:
    for c in coins:
        if c <= a and best[a - c] + 1 == best[a]:
            chosen.append(c)
            a -= c
            break

Find the neighbour consistent with this cell's value, which is the same backward walk used for knapsack and longest common subsequence.