Coin Change Algorithm

The advent of paper money in the mid-17th century and the development of modern banking and floating exchange rates in the 20th century allowed a foreign exchange market to develop. This provided a manner for banks and other specialist fiscal company such as bureaux de change and forex brokers to easily change one state's money for another, and with the added confidence of transparency. 

When outsiders, particularly traveling merchants, visited towns for a market fair, it became necessary to exchange foreign coins to local ones at local money changers. The merchant could then withdraw the money in local currency to conduct trade or, more likely, keep it deposited: the money changer would act as a clearing facility. In ancient times in Jerusalem, pilgrims visiting the Jewish Temple on Jewish Holy day would change some of their money from the standard Greek and Roman currency for Jewish and Tyrian money,
package DynamicProgramming;

/**
 * @author Varun Upadhyay (https://github.com/varunu28)
 */
public class CoinChange {

    // Driver Program
    public static void main(String[] args) {

        int amount = 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
     **/
    public static int change(int[] coins, int amount) {

        int[] combinations = new int[amount + 1];
        combinations[0] = 1;

        for (int coin : coins) {
            for (int i = 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);
        }

        return combinations[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 the minimum number of coins that make a given value.
     **/
    public static int minimumCoins(int[] coins, int amount) {
        //minimumCoins[i] will store the minimum coins needed for amount i
        int[] minimumCoins = new int[amount + 1];

        minimumCoins[0] = 0;

        for (int i = 1; i <= amount; i++) {
            minimumCoins[i] = Integer.MAX_VALUE;
        }
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    int sub_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);
        return minimumCoins[amount];
    }

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

LANGUAGE:

DARK MODE: