How do you solve the coin change problem?

Question presented to candidate: "You are given coin denominations and a target amount. Return the fewest coins needed to make that amount exactly, or -1 if it cannot be made; you have an unlimited supply of each coin. Explain why the obvious greedy idea does not work, then code a solution in Python."

What a strong answer should cover:

• Why greedy (always take the biggest coin) is wrong in general: with coins [1, 3, 4] and amount 6 it uses 4 + 1 + 1 = 3 coins, but 3 + 3 = 2 coins is optimal.
• The DP state and recurrence: dp[a] = fewest coins that make a; dp[0] = 0; dp[a] = 1 + min(dp[a - c]) over coins c <= a; an "impossible" sentinel such as amount + 1.
• O(amount × number of coins) time and O(amount) space, and why it is pseudo-polynomial (it depends on the value of amount, not its digit count).
• Rebuilding the actual coins by storing the last coin used per amount, and the related "number of ways" variant, where the loop order decides whether you count combinations or orders.
• Python details: a list [0] + [INF] * amount, amount + 1 (or float("inf")) as the sentinel, and functools.lru_cache for a top-down version, which hits the default recursion limit of 1000 for large amounts.

Clarifying questions expected:

• Is the supply of each coin unlimited, and are all coin values positive?
• What should be returned when the amount cannot be made, and what for amount 0?
• Do you need the count only, or also which coins to use?

Code / implementation expected: Yes — a bottom-up Python function over amounts 0..amount; rebuilding the coins used is a common follow-up.