Coin Change — Interview Guide

• dp[a] = minimum coins to make amount a.
• dp[a] = 1 + min(dp[a - coin]) over all coins ≤ a.
• Greedy (always take the largest coin) fails on some denominations — interviewers love this counter-example.

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