Coin Change

MediumArray Dynamic Programming BFS

A vending machine has to pay out exactly amount cents in change. It holds an unlimited supply of coins of every denomination in coins, and to keep any one coin tube from running empty, it wants to pay with as few coins as possible.

Return the smallest number of coins that add up to exactly amount. If no combination of the available denominations reaches that amount, return -1. Paying out 0 cents takes 0 coins.

Example 1

Input: coins = [1,6,10], amount = 12
Output: 2

Explanation: 6 + 6 uses two coins. Taking the largest coin first gives 10 + 1 + 1, which uses three.

Example 2

Input: coins = [4,6], amount = 9
Output: -1

Explanation: Every coin is even, so no combination can reach an odd amount.

Example 3

Input: coins = [2,5], amount = 11
Output: 4

Explanation: 5 + 2 + 2 + 2. Using two 5s would leave 1, which no coin can pay.

Constraints

There are between 1 and 12 denominations.
Each denomination is between 1 and 2^31 - 1 cents.
amount is between 0 and 10^4.

Follow-up: Instead of the fewest coins, how would you count how many different combinations of coins pay out the amount?

💡 Hint 1

Greedy (always take the biggest coin that fits) is wrong for many coin systems, as the first example shows.

💡 Hint 2

Let dp[a] be the fewest coins for amount a. Then dp[a] = 1 + min(dp[a - c]) over every coin c <= a.

💡 Hint 3

Fill dp from 0 up to amount, using a sentinel such as amount + 1 for "unreachable".

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Bottom-up DP over amounts. dp[0] = 0 and every other entry starts at the sentinel amount + 1 (more coins than could ever be needed). For each amount a from 1 to amount, try every coin c <= a: dp[a] = min(dp[a], dp[a - c] + 1). If dp[amount] is still the sentinel, the amount is unreachable. Comparing c <= a before subtracting also keeps huge coin values from overflowing.

Time O(amount · k) for k coin typesSpace O(amount)

function coinChange(coins, amount) {
  const INF = amount + 1;
  const dp = new Array(amount + 1).fill(INF);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
    }
  }
  return dp[amount] === INF ? -1 : dp[amount];
}

class Solution {
    public int coinChange(int[] coins, int amount) {
        int inf = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, inf);
        dp[0] = 0;
        for (int a = 1; a <= amount; a++) {
            for (int c : coins) {
                if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
            }
        }
        return dp[amount] == inf ? -1 : dp[amount];
    }
}

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
function coinChange(coins, amount) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit