Coin change problem

Find the minimum number of coins required to make change of N, given currencies of different values.

E.g.,

Input: Denominations {1,3,5,8,9},   Value: 28
Output: 4


This problem can be solved using dynamic programming approach. This is similar to Knapsack problem.

Below is Java implementation

public class CoinChange {

    public static void main(String args[])
    {
        int []denominations = {1,3,5,8,9};
        int value = 28;
        System.out.println("The minimum number of coins required to make change of "+value+" is:"+findMinimumCoinsRequired(denominations,value));
    }

    private static int findMinimumCoinsRequired(int[] denominations, int value) {
       
        int []dp = new int[value+1];       
        dp[0] = 0;

        for(int i = 1; i <= value; i++ )
        {
            dp[i] = Integer.MAX_VALUE;
            for( int j = 0; j < denominations.length; j++ )
            {
                if( denominations[j] <=  i  )
                {
                    dp[i] = Math.min(dp[i], dp[i - denominations[j]]+1);
                }
            }
        }
        return dp[value];
    }
}