content: package dynamicprogramming;
  
  
  public class CoinChangingProblem {
  
      /*
       * Given coin denominations and the total amount, find out the number​ of ways to make the change.
       * Denominations: 1, 2, 5
       * Amount: 7
       * Total Methods: 6
       *
       * Runtime Complexity:
       * O(m n) where m is number of denominations and n is amount.
       *
       * Memory Complexity:
       * Linear, O(n) where n is the amount.
       *
       * Dynamic programming is a problem solving approach which is used when naive approach results in
       * exponential time complexity. To apply dynamic programming approach, the problem to be solved must
       * have optimal substructure i.e. optimal solution of the problem at hand could be achieved by
       * leveraging the optimal solutions of its subproblems and overlapping sub-problems i.e. using
       * pre-computed values for solved sub-problems so that we don't have to solve them again.
       * The coin changing problem has both optimal substructure i.e it can be easily divided to simpler
       * problems and they can be solved to find final solution and it also satisfies the property of
       * overlapping sub problems i.e. previously solved sub problem results can be used multiple times.
       *
       *
       * */
      protected static int solveCoinChangeDp(int[] denominations,
                                             int amount) {
  
  
          int[] solution = new int[amount + 1];
          solution[0] = 1;
  
          for (int den : denominations) {
              for (int i = den; i < (amount + 1); ++i) {
                  solution[i] += solution[i - den];
              }
          }
          return solution[solution.length - 1];
      }
  
  
      public static void main(String[] args) {
          int[] denominations = new int[]{1, 5, 10};
          System.out.println("Combinations (DP): " + solveCoinChangeDp(denominations, 356));
      }
  }
  