Coin Change

Given coin denominations coins and a target amount, return the fewest coins needed to make that amount. You have unlimited coins of each denomination. If it can't be made, return -1.

Examples

Input:  coins = [1,2,5], amount = 11   -> 3     # 5 + 5 + 1
Input:  coins = [2],      amount = 3    -> -1
Input:  coins = [1],      amount = 0    -> 0

Constraints

• 1 <= len(coins) <= 12, 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

Approach — bottom-up DP over amounts

Greedy (always take the biggest coin) fails: for coins=[1,3,4], amount=6, greedy gives 4+1+1=3 coins but the optimum is 3+3=2. So we need DP.

Define dp[a] = fewest coins to make amount a. To make a, try each coin c: if you use one c, the rest costs dp[a - c]. Take the minimum over all coins:

dp[a] = min(dp[a - c] + 1 for c in coins if c <= a)

Base case dp[0] = 0 (zero coins make zero). Seed the rest with a sentinel meaning "unreachable."

Solution

def coin_change(coins: list[int], amount: int) -> int:
    INF = amount + 1                      # more than any real answer
    dp = [0] + [INF] * amount             # dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

Explanation

• Why bottom-up works: every dp[a - c] is a smaller amount, already computed before we reach a, so each subproblem is solved once and reused.
• The sentinel INF = amount + 1 is larger than any achievable coin count (you can't use more than amount coins of value ≥ 1), so min naturally ignores unreachable states. If dp[amount] is still INF at the end, the amount is impossible → -1.
• Why greedy fails is worth stating: locally optimal coin picks can strand you with an awkward remainder.

Complexity

• Time: O(amount * len(coins)).
• Space: O(amount).

Interview tips

This is the canonical unbounded knapsack. Lead with a concrete greedy counterexample — proving greedy is wrong is often what earns the DP. A follow-up ("count the number of combinations") flips the inner/outer loop order; be ready to discuss why.