Coin Change

medium dp

Problem

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Inputcoins = [1, 2, 5], amount = 11

Output3

dp[a] = fewest coins summing to a. dp[0] = 0; dp[a] = min over coins c of dp[a − c] + 1, when a ≥ c.

coins

amount

def coin_change(coins, amount):
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0
    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 -1 if dp[amount] == INF else dp[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] = Math.min(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] = Math.min(dp[a], dp[a - c] + 1);
            }
        }
        return dp[amount] == INF ? -1 : dp[amount];
    }
}

int coinChange(vector<int>& coins, int amount) {
    int INF = amount + 1;
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (c <= a) dp[a] = min(dp[a], dp[a - c] + 1);
        }
    }
    return dp[amount] == INF ? -1 : dp[amount];
}

Explanation

Here we want the fewest coins that add up to amount. We build the answer from the bottom up: solve every smaller amount first, then use those to solve the bigger ones.

dp[a] means "the smallest number of coins that sum to a". We start with dp[0] = 0 (zero coins make zero) and fill everything else with a large placeholder INF = amount + 1 meaning "not reachable yet".

For each amount a from 1 upward, we try every coin c. If c <= a, then one way to make a is to take the best solution for a - c and add one more coin: dp[a] = min(dp[a], dp[a - c] + 1).

At the end, if dp[amount] is still the placeholder, the amount can't be formed and we return -1; otherwise dp[amount] is the answer.

Example: coins = [1, 2, 5], amount = 11. The best is 5 + 5 + 1, so dp[11] = 3.

Time: O(amount · |coins|) Space: O(amount)