322. Coin Change

Problem¶

Given unlimited coins of given values, return the minimum number of coins needed to make amount, or -1 if impossible.

• Example:

  coins = [1, 2, 5], amount = 11 -> 3
  because 11 = 5 + 5 + 1
  

Key trick¶

Use dynamic programming on all amounts from 0 to amount.

• Let dp[a] be the minimum coins needed to make amount a.
• Transition:

  dp[a] = min(dp[a], dp[a - coin] + 1)    for every coin <= a
  

• Initialize:

  dp[0] = 0
  dp[others] = amount + 1
  

Trap¶

• Greedy does not work in general.
  • Example:

    coins = [1, 3, 4], amount = 6
    greedy -> 4 + 1 + 1 = 3
    best   -> 3 + 3 = 2
    

• Forgetting unreachable states and returning a fake large value instead of -1.
• Using backtracking only, which is too slow.

Why is it interesting?¶

It looks greedy, but the real solution is classic unbounded knapsack DP.

• It tests:
  • recognizing when greedy fails
  • building a 1D DP
  • handling impossible states cleanly

Python solution¶

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        # dp[a] = minimum number of coins needed to make amount a
        # Start with an impossible large value.
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0

        # Build answers bottom-up.
        for a in range(1, amount + 1):
            for coin in coins:
                if coin <= a:
                    dp[a] = min(dp[a], dp[a - coin] + 1)

        # If still impossible, return -1.
        return dp[amount] if dp[amount] != amount + 1 else -1

• Complexity:
  • Time: \(O(\text{amount} \cdot |\text{coins}|)\)
  • Space: \(O(\text{amount})\)

Comment on my solution¶

Your notes are going in the right direction by questioning greedy, but the key mistake is still hoping larger coins should be prioritized.

• Good:
  • you noticed brute force is too big
  • you suspected greedy needs justification
  • you checked edge cases like amount = 0
• Problem:
  • sorting descending and taking bigger coins first is not correct in general
  • parity observations like odd/even help only in narrow cases
• Interview pivot:
  • after showing greedy fails on a counterexample, switch quickly to 1D DP

## Solution

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        # coins = [1,2,5], amount = 11 -> 3 (1 + 5 + 5 == 11)
        # coins = [2], amount = 3 -> -1
        # coins = [1], amount = 0 -> 0
        # - 2 questions:
        #   - does it exist x1, ..., xn such
        #     x1*coins[0] + ... + xn*coins[n-1] == amount
        #   - take the (x1, ..., xn) that minimize sum(x1, ..., xn)
        # - Brute force:
        #   - for each coin in coins compute x such
        #     x*coin <= amount < (x + 1)*coin
        #   - then try all combination and stop early
        # - To minimize sum(x1, ..., xn) we should prioritize bigger coins
        #   - so maybe sort coins in descending order
        # - if amount % 2 == 1, we need at least on odd number in coins