322. Coin Change

← All Problems
medium Dynamic Programming
Given an array of integer coin denominations and a target amount, return the fewest number of coins needed to make up that amount. You may use each coin denomination an unlimited number of times. If no combination of coins can produce the target amount, return -1. The number of coin types can be up to 12 and the amount can be up to 10,000.

Example

coins = [1, 3, 4], amount = 6

Output: 2

Because 3 + 3 = 6, which uses only 2 coins. Other combinations like 4 + 1 + 1 use 3 coins, and 1 + 1 + 1 + 1 + 1 + 1 uses 6.

dp[amount] stores the minimum number of coins needed. For each amount from 1 up to the target, try every coin denomination: dp[i] = min(dp[i], dp[i - coin] + 1). If dp[i - coin] was reachable, using one more coin of this type might improve the answer for amount i.

Why this works

To make amount i with the fewest coins, you can try adding one coin of each denomination to the best solution for i - coin. By building up from amount 0, every smaller sub-problem is already solved when you need it, so you always pick the true minimum.

Step by step

  1. Create a DP array — dp[i] will hold the minimum coins for amount i. Initialize everything to infinity (unreachable) except dp[0] = 0.
  2. Build up from 1 to target — for each amount i, try subtracting each coin denomination.
  3. Take the best option — if dp[i - coin] + 1 is fewer coins than what you currently have for dp[i], update it.
  4. Check the answer — if dp[amount] is still infinity, the amount is impossible, so return -1.
Time: O(amount × coins) Space: O(amount) 
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1); // sentinel larger than any valid answer
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1); // use this coin if it gives fewer total
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1); // sentinel larger than any valid answer
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = min(dp[i], dp[i - coin] + 1); // use this coin if it gives fewer total
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

def coinChange(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)  # inf means "not yet reachable"
    dp[0] = 0  # base case: 0 coins needed for amount 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)  # use this coin if it gives fewer total
    return dp[amount] if dp[amount] != float('inf') else -1