Coin Change in Interviews: Minimum Coins vs Number of Ways
Coin Change comes in two versions that look identical but need different loops. Interviewers often ask one and then the other to see if you really understand the DP.
Version 1: fewest coins to make an amount
dp[a] = minimum coins to make amount a. dp[0] = 0, everything else starts at infinity.
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
Return -1 if dp[amount] is still infinity. Mention why greedy fails: with coins 1, 3, 4 and amount 6, greedy picks 4+1+1 but 3+3 is better.
Version 2: number of combinations
dp[a] = number of ways to make a. dp[0] = 1. Now the coin loop must be outside:
for c in coins:
for a in range(c, amount + 1):
dp[a] += dp[a - c]
If you swap the loops, you count permutations (1+2 and 2+1 separately), which answers a different question (Combination Sum IV).
Complexity
Both are O(amount * number of coins) time and O(amount) space.
In the interview
State the recurrence before writing code, and walk through a tiny example like coins [1, 2] and amount 3. If you want feedback on how clearly you explain DP under time pressure, an AI tool for job interviews like Linkjob AI can run mock rounds with you.
Disclosure: I work on Linkjob AI.