Minimum Coins for Change Solution

gistfile1.md

The first approach that jumps to mind for most people is using a greedy algoirthm- picking the biggest coin possible and continuing to do this until you have the amount you are looking for.

This looks something like this:

function minCoins(coinArr, amt) {
    var numCoins = 0;
    while (amt !== 0) {
        var eligibleCoins = coinArr.filter(function(coin) {
            return coin <= amt;
        });
        if (!eligibleCoins.length)
            return 'The amount of change you indicated can not be made with these coins '
        var choice = Math.max.apply(null, eligibleCoins);
        numCoins++;
        amt -= choice;
    }
    return numCoins
}

This approach of always picking the largest coin possible works in most cases. It actually always finds the optimal number of coins when your coin possibilities are the standard US coins (i.e. coinArr = [1,5,10,25]). However let's think about some possibilities when this won't return the optimal result.

What if your possible coins are [1,4,6] and the amount you are making change for is 8? The greedy approach would be to pick 6 and then 1 and then 1 again for a total of 3 coins.

But the minimum number of coins is actually 2– picking 4 and then 4 again. Let's think about how we can get that result:

If the amount is 1 or 4 or 6, the minimum number of coins is 1 (you just pick the coin with the value you want).

What if you have another amount?

If we want to make change for an amount n, the minimum number of coins is going to be:

Why? Because you can add either a coin of value 6 to the minimum number of coins for n-6, a coin of value 4 to the minimum number of coins for n-4, or a coin of value 1 to the minimum number of coins for n-1.

Following this logic, we can write the following recursive function to calculate the minimum number of coins. Since we are using previous results to generate our answer, this would be considered a dynamic programming approach. Here is one way to do this:

function minimalCoins(coins, amt) {
    var mem = { };
    mem[0] = 0;
    function calculateChange(coins, curAmt) {
        if (typeof mem[curAmt] !== 'undefined' )
            return mem[curAmt];
        if (mem[curAmt])
          return mem[curAmt];
        if (coins.indexOf(curAmt) > -1) {
            mem[curAmt] = 1;
            return 1;
        }
        var curMin = Number.MAX_VALUE;
        coins.forEach(function(coin) {
            if (coin < curAmt)
                curMin = Math.min(curMin,1 + calculateChange(coins, curAmt-coin) );
        });
        mem[curAmt] = curMin;
        return curMin;
    }
    return calculateChange(coins, amt);
}