Explain the Coin Change problem.

Short answer: Unbounded knapsack DP: dp[a] = minimum coins to make amount a. For each coin, update dp[x] = min(dp[x], dp[x - coin] + 1). Initialize dp[0] = 0 and others to +∞. Return -1 if unreachable.

Complexity

Time O(amount * coins), Space O(amount).

Edge cases to mention

• Amount 0 → 0
• No combination possible → -1
• Coin larger than amount

Common follow-ups

• Coin Change II — number of combinations
• Fewest coins with limited supply

Mention top-down memoization as an alternative to bottom-up.