Apply the dynamic programming algorithm to find all the solu

Apply the dynamic programming algorithm to find all the solutions to the change-making problem for the denominations 1, 3, 5 and the amount n=9.

Solution

Here we have three condition to check
1) if provided n is equal to 0 then we will return empty set to make chages.
2) if no coins given, 0 ways to change the n (that means denomination is not provided)
3) if the coin value is less than the n needed then reduce the n by coin value & use the subproblem solution (n-v[i]) & add the solution from the top to it else just copy the value from top.

class ChangeMakingProblem
{
public static int dynamic(int[] v, int n) {
       int[][] solution = new int[v.length + 1][n + 1];

       for (int i = 0; i <= v.length; i++) {
           solution[i][0] = 1;
       }

       for (int i = 1; i <= n; i++) {
           solution[0][i] = 0;
       }

       // now as per our given scenario
       for (int i = 1; i <= v.length; i++) {
           for (int j = 1; j <= n; j++) {
              
               if (v[i - 1] <= j) {
                  
                   solution[i][j] = solution[i - 1][j]
                           + solution[i][j - v[i - 1]];
               } else {
                   // just copy the value from the top
                   solution[i][j] = solution[i - 1][j];
               }
           }
       }
       return solution[v.length][n];
   }
   public static void main(String[] args) {
       int n = 9;
       int[] v = { 1, 3, 5 };
       System.out.println(\"Change making problem solution by Dynamic Algorithm \" + dynamic(v, n));
   }
  
}