Minimum number of coins required to make a sum - PrismoSkills

Minimum number of coins required to make a sum - PrismoSkills
Suppose we knew the minimum no of coins required to form sum 0 to S for coins 0 to k, then introduction of another coin k+1 should change all minimum coins from 0 to S as follows:
If minCoins[S] < 1 + minCoins[S-(k+1)], change the minCoins count at Sum S
int findMinCoins (int Sum, int denoms [])
{
    int lookup[Sum+1] = {0};

    for (int i=0; i&lt;denoms.length; i++)
    {
        for (int S=1; S&lt;=Sum; S++)
        {
            if (S &gt; denoms[i])
            {
                int minCoinsWithNewCoin = lookup[S-denom[i]] + 1;
                if (minCoinsWithNewCoin &lt; lookup[S] || lookup[S]==0)
                    lookup[S] = minCoinsWithNewCoin;
            }
        }
    }

    return lookup[Sum];
}

Find min number of coins and also print the denominations in solution

Since lookup[S_i] has been expressed in terms of lookup[S_j] where S_j < S_i, the difference between S_i and S_j gives us the denomination of one of the coin.

So, if store the first denomination required at each stage, then we can use it to get from S_i to S_j. At S_j, we can check the denomination stored there to go further below and so on

int findMinCoins (int Sum, int denoms [])
{
    int lookup[Sum+1] = {0};
    int biggestDenomAtSumK[Sum+1] = {-1};

    for (int i=0; i&lt;denoms.length; i++)
    {
        for (int S=1; S&lt;=Sum; S++)
        {
            if (S &gt; denoms[i])
            {
                int minCoinsWithNewCoin = lookup[S-denom[i]] + 1;
                if (minCoinsWithNewCoin &lt; lookup[S] || lookup[S]==0)
                {
                    lookup[S] = minCoinsWithNewCoin;
                    biggestDenomAtSumK[S] = denom[i];
                }
            }
        }
    }

    int S=Sum;
    while (S &gt; 0)
    {
        System.out.println (biggestDenomAtSumK[S]);
        S = S - biggestDenomAtSumK[S];
    }

    return lookup[Sum];
}

Another way of looking at this problem is that we can think each combination of coins as a solution to the equation

d₀x + d₁y + d₂z .... d_i p + d_mq = N

Where N is the sum we need to count using the coins,

d_i is i^th denomination in the coins’ denomination array.

and x, y, z ... p, q are the coefficients whose different values provide us all the solutions to this problem

https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/CoinChangingMinimumCoin.java
    public int minimumCoinTopDown(int total, int coins[], Map<Integer, Integer> map) {

        //if total is 0 then there is nothing to do. return 0.
        if ( total == 0 ) {
            return 0;
        }

        //if map contains the result means we calculated it before. Lets return that value.
        if ( map.containsKey(total) ) {
            return map.get(total);
        }

        //iterate through all coins and see which one gives best result.
        int min = Integer.MAX_VALUE;
        for ( int i=0; i < coins.length; i++ ) {
            //if value of coin is greater than total we are looking for just continue.
            if( coins[i] > total ) {
                continue;
            }
            //recurse with total - coins[i] as new total
            int val = minimumCoinTopDown(total - coins[i], coins, map);

            //if val we get from picking coins[i] as first coin for current total is less
            // than value found so far make it minimum.
            if( val < min ) {
                min = val;
            }
        }

        //if min is MAX_VAL dont change it. Just result it as is. Otherwise add 1 to it.
        min =  (min == Integer.MAX_VALUE ? min : min + 1);

        //memoize the minimum for current total.
        map.put(total, min);
        return min;
    }
Read full article from Minimum number of coins required to make a sum - PrismoSkills