55. Coin Change

You are given the coin denominations coins (you have an unlimited supply of each) and a target amount.

Return the fewest coins whose values add up to exactly amount. If no combination of coins makes that amount, return -1. An amount of 0 needs 0 coins.

Example 1

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

Explanation: 4 + 4 = 8. Grabbing the largest coin first gives 5 + 1 + 1 + 1, which uses 4 coins.

Example 2

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

Explanation: Multiples of 3 never reach 4.

Example 3

Input: coins = [2], amount = 0
Output: 0

Constraints

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

Follow-up: How would you count the number of different combinations that make up the amount, instead of the minimum?

💡 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