💬 Discord
Sign In
NeetCode #669LC-322Medium1-D Dynamic ProgrammingBlind 75NC 150NC 250
← Back to All Problems

#669 · #322 · Coin Change(零钱兑换)

📌 Problem Statement & Constraints

You are given an integer array coins of distinct denominations and an integer amount. You have an unlimited supply of each coin. Return the fewest coins needed to make up amount, or -1 if it cannot be formed. Constraints: 1 <= coins.length <= 12, 1 <= coins[i] <= 2^31 - 1, 0 <= amount <= 10^4.

💡 Core Algorithmic Approaches

  1. Let dp[a] be the minimum number of coins needed to make amount a; initialise dp[0] = 0 and every other entry to infinity.
  2. For each amount from 1 to amount, try every coin c <= a and relax dp[a] = min(dp[a], dp[a - c] + 1).
  3. The base dp[0] = 0 represents the empty selection, and unreachable amounts remain infinite.
  4. Map the infinite sentinel to -1 at the end.

💻 Benchmark Python3 Implementation

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        INF = float("inf")
        dp = [0] + [INF] * amount
        for a in range(1, amount + 1):
            for c in coins:
                if c <= a and dp[a - c] + 1 < dp[a]:
                    dp[a] = dp[a - c] + 1
        return dp[amount] if dp[amount] != INF else -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(amount * len(coins)): the amount loop times the coin loop.
💾 Space Complexity
O(amount): the DP array.

⚠️ Interview Pitfalls & Follow-ups

  • Using a greedy largest-coin-first strategy: it fails for coins = [1, 3, 4] and amount = 6, where greedy takes 4 + 1 + 1 (3 coins) while 3 + 3 is optimal (2 coins).
  • Initialising dp[0] to infinity: every transition then stays infinite; the base must be 0.
  • Looping the coins outside and amounts inside: that counts ordered permutations, which is problem 377, not this one.
  • Returning dp[amount] without the infinity guard: impossible amounts must report -1.