CoinChange.java

packagecom.thealgorithms.dynamicprogramming;

/**
 * @author Varun Upadhyay (https://github.com/varunu28)
 */
publicclassCoinChange {

// Driver Program
publicstaticvoidmain(String[] args) {
intamount = 12;
int[] coins = {2, 4, 5};

System.out.println("Number of combinations of getting change for " + amount
 + " is: " + change(coins, amount));
System.out.println("Minimum number of coins required for amount :" + amount
 + " is: " + minimumCoins(coins, amount));
 }

/**
 * This method finds the number of combinations of getting change for a
 * given amount and change coins
 *
 * @param coins The list of coins
 * @param amount The amount for which we need to find the change Finds the
 * number of combinations of change
 */
publicstaticintchange(int[] coins, intamount) {
int[] combinations = newint[amount + 1];
combinations[0] = 1;

for (intcoin : coins) {
for (inti = coin; i < amount + 1; i++) {
combinations[i] += combinations[i - coin];
 }
// Uncomment the below line to see the state of combinations for each coin
// printAmount(combinations);
 }

returncombinations[amount];
 }

/**
 * This method finds the minimum number of coins needed for a given amount.
 *
 * @param coins The list of coins
 * @param amount The amount for which we need to find the minimum number of
 * coins. Finds the minimum number of coins that make a given value.
 */
publicstaticintminimumCoins(int[] coins, intamount) {
// minimumCoins[i] will store the minimum coins needed for amount i
int[] minimumCoins = newint[amount + 1];

minimumCoins[0] = 0;

for (inti = 1; i <= amount; i++) {
minimumCoins[i] = Integer.MAX_VALUE;
 }
for (inti = 1; i <= amount; i++) {
for (intcoin : coins) {
if (coin <= i) {
intsub_res = minimumCoins[i - coin];
if (sub_res != Integer.MAX_VALUE && sub_res + 1 < minimumCoins[i]) {
minimumCoins[i] = sub_res + 1;
 }
 }
 }
 }
// Uncomment the below line to see the state of combinations for each coin
// printAmount(minimumCoins);
returnminimumCoins[amount];
 }

// A basic print method which prints all the contents of the array
publicstaticvoidprintAmount(int[] arr) {
for (inti = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
 }
System.out.println();
 }
}