Please write the algorithm in Java comments on code will be

Please write the algorithm in Java. comments on code will be helpful

2. (15 points) Design algorithm for the coin change problem using dynamic programming approach, and implement your algorithm. [Demo required in the week of Oct 10hl. Analyze the time complexity of the algorithm Given coin denominations by value: ci

Solution

// CoinChange.java
public class CoinChange
{
   public static int count(int[] coins, int inputAmount)
   {
   if(inputAmount==0) return 0;
     
      // minNumCoins[] is minimum number of coins required to get the inputAmount
   int[] minNumCoins = new int [inputAmount+1];
   minNumCoins[0]=0; // no need of any coin to get 0
   for(int i=1;i<=inputAmount; i++)
       // initially set minNumCoins[i] to be MAX_VALUE.
   minNumCoins[i]= Integer.MAX_VALUE;
     
   for(int i=0; i<=inputAmount; i++)
   {
   for(int c: coins)
   {
   if(i+c <=inputAmount)
   {
   if(minNumCoins[i]==Integer.MAX_VALUE)
   {
       // minNumCoins[i+coin] = minNumCoins[i+coin] is minNumCoins[i] is not reachable.
   minNumCoins[i+c] = minNumCoins[i+c];
   }
   else
   {
       // minNumCoins[i+coin] = min(minNumCoins[i+coin], minNumCoins[i]+1) if minNumCoins[i] is reachable
   minNumCoins[i+c] = Math.min(minNumCoins[i+c], minNumCoins[i]+1);
   }
   }
   }
   }
     
   if(minNumCoins[inputAmount] >= Integer.MAX_VALUE)
   return -1;
     
   return minNumCoins[inputAmount];
   }

   // driver main function
   public static void main(String[] args)
   {
       int coins[]=new int[4];//declaration and instantiation
       coins[0]=1;//initialization
       coins[1]=5;
       coins[2]=10;
       coins[3]=25;

       System.out.println(\"Total: \"+ count(coins,78) + \" coins\");
   }
}

/*
since there are two nested for loops involved which iterates over the coins array
Time complexity: O(n^2)

output:
Total: 6 coins

*/