Coin Change Problem

Coin Change Problem:


Given set of n coins what is the minimum no of coins required to make an amount P.

This problem can be solved using Dynamic programming, we need to find out the minimum no of coins for the
amount less than P and add 1 additional coin. So to start with, lets consider some example

Coins = {1,2,3}
Amount = 5

C(0)=0 // no coins for amount 0.

To make change of p , say C(P) = Min{ C(p-Vi) } + 1 for i from 1 to n, i<=P
C(1) = Min { C(1-1) } + 1 = C(0) + 1 = 1
C(2) = Min { C(2-1),C(2-2)}+1 = Min { C(1),C(0) } + 1 = Min { 1,0 } + 1 = 1
C(3) = Min { C(3-1),C(3-2),C(3-3)}+1 = Min { C(2),C(1),C(0) } + 1 = Min { 1,1,0 } + 1 = 1
C(4) = Min { C(4-1),C(4-2),C(4-3)}+1 = Min { C(3),C(2),C(1) } + 1 = Min { 1,1,1 } + 1 = 2
C(5) = Min { C(5-1),C(5-2),C(5-3)}+1 = Min { C(4),C(3),C(2) } + 1 = Min { 2,1,1 } + 1 = 2

So, to make a change of 5 using denominations (1,2,3) , we need min of 2 coins.

C++ Code:

int coinChange(int a[],int n,int Sum)
{
    int *S = new int[Sum+1];
    for(int i=0;i<Sum+1;i++)
        S[i]=INT_MAX;

    S[0]=0; // To make amount of zero we need 0 coins.
   
    for(int i=a[0];i<=Sum;i++)  //Start with a[0] thats the min amount for which you get can get change.
    {
        for(int j=0;j<n;j++)
        {
            if(i>=a[j] && S[i-a[j]]+1<S[i])
            {
            S[i]=S[i-a[j]]+1;
            cout<<" I is :"<<i<<" min coins for "<<i<<" is :"<<S[i]<<endl;
            }
        }
    }
    return S[Sum];
}

int main()
{
int arr[] = {5,10, 20}; 
int m = sizeof(arr)/sizeof(arr[0]); 
int n = 30; 
cout<<" Min coins to make "<<n<<" is :"<<coinChange(arr,3,n)<<endl;
return(0);
}

Java Code:
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];
    }
}