Coin Change

Medium Dynamic Programming

Given coin denominations and an amount, return the fewest coins needed to make that amount, or -1 if impossible. Classic bottom-up DP.

Sample input

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

Sample output

Solution

def coin_change(coins, amount):
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)
    return dp[amount] if dp[amount] != float("inf") else -1

print(coin_change([1, 2, 5], 11))

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (const coin of coins) {
    for (let x = coin; x <= amount; x++) {
      dp[x] = Math.min(dp[x], dp[x - coin] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(coinChange([1, 2, 5], 11));

import java.util.Arrays;

public class Main {
    static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int coin : coins) {
            for (int x = coin; x <= amount; x++) {
                dp[x] = Math.min(dp[x], dp[x - coin] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1, 2, 5}, 11));
    }
}

fun coinChange(coins: IntArray, amount: Int): Int {
    val dp = IntArray(amount + 1) { amount + 1 }
    dp[0] = 0
    for (coin in coins) {
        for (x in coin..amount) {
            dp[x] = minOf(dp[x], dp[x - coin] + 1)
        }
    }
    return if (dp[amount] > amount) -1 else dp[amount]
}

fun main() {
    println(coinChange(intArrayOf(1, 2, 5), 11))
}

func coinChange(_ coins: [Int], _ amount: Int) -> Int {
    var dp = [Int](repeating: amount + 1, count: amount + 1)
    dp[0] = 0
    for coin in coins where coin <= amount {
        for x in coin...amount {
            dp[x] = min(dp[x], dp[x - coin] + 1)
        }
    }
    return dp[amount] > amount ? -1 : dp[amount]
}

print(coinChange([1, 2, 5], 11))

int coinChange(List<int> coins, int amount) {
  final dp = List.filled(amount + 1, amount + 1);
  dp[0] = 0;
  for (final coin in coins) {
    for (var x = coin; x <= amount; x++) {
      if (dp[x - coin] + 1 < dp[x]) dp[x] = dp[x - coin] + 1;
    }
  }
  return dp[amount] > amount ? -1 : dp[amount];
}

void main() {
  print(coinChange([1, 2, 5], 11));
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int coinChange(const vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int coin : coins) {
        for (int x = coin; x <= amount; x++) {
            dp[x] = min(dp[x], dp[x - coin] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

int main() {
    cout << coinChange({1, 2, 5}, 11) << endl;
    return 0;
}

#include <stdio.h>

int coinChange(int *coins, int numCoins, int amount) {
    int dp[amount + 1];
    for (int i = 0; i <= amount; i++) dp[i] = amount + 1;
    dp[0] = 0;
    for (int c = 0; c < numCoins; c++) {
        for (int x = coins[c]; x <= amount; x++) {
            if (dp[x - coins[c]] + 1 < dp[x]) dp[x] = dp[x - coins[c]] + 1;
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

int main() {
    int coins[] = {1, 2, 5};
    printf("%d\n", coinChange(coins, 3, 11));
    return 0;
}