CoinChange.java

packagecom.thealgorithms.dynamicprogramming;

/**
 * @author Varun Upadhyay (https://github.com/varunu28)
 */
publicfinalclassCoinChange {
privateCoinChange() {
 }

/**
 * 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];
 }
 }

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) {
intsubRes = minimumCoins[i - coin];
if (subRes != Integer.MAX_VALUE && subRes + 1 < minimumCoins[i]) {
minimumCoins[i] = subRes + 1;
 }
 }
 }
 }

returnminimumCoins[amount];
 }
}