content: package by.andd3dfx.dynamic;
  
  import java.util.Arrays;
  
  import static java.lang.Integer.MAX_VALUE;
  
  /**
   * <pre>
   * <a href="https://www.geeksforgeeks.org/find-minimum-number-of-coins-that-make-a-change/?ref=lbp">Task description</a>
   *
   * Given a value V, if we want to make a change for V cents, and we have an infinite supply of each of
   * C = { C1, C2, .., Cm} valued coins, what is the minimum number of coins to make the change?
   * If it’s not possible to make a change, print -1.
   *
   * Examples:
   *     Input: coins[] = {25, 10, 5}, V = 30
   *     Output: Minimum 2 coins required. We can use one coin of 25 cents and one of 5 cents
   *
   *     Input: coins[] = {9, 6, 5, 1}, V = 11
   *     Output: Minimum 2 coins required. We can use one coin of 6 cents and 1 coin of 5 cents
   * </pre>
   *
   * @see <a href="https://youtu.be/K1xPbYPslRU">Video solution</a>
   */
  public class ChangeWithMinNumberOfCoins {
  
      public static int determine_usingRecursion(int[] coins, int amount) {
          Arrays.sort(coins);
          var result = innerRecursion(coins, amount);
  
          if (result == MAX_VALUE) {
              return -1;
          }
          return result;
      }
  
      private static int innerRecursion(int[] coins, int amount) {
          if (amount == 0) {
              return 0;
          }
  
          int result = MAX_VALUE;
          for (var coin : coins) {
  
              // Go through all coins smaller or equals to `amount`
              if (amount >= coin) {
                  int subResult = innerRecursion(coins, amount - coin);
  
                  // Check for INT_MAX to avoid overflow and see if a result can be minimized
                  if (subResult != MAX_VALUE && subResult + 1 < result) {
                      result = subResult + 1;
                  }
              }
          }
  
          return result;
      }
  
      public static int determine_usingMemoization(int[] coins, int amount) {
          // The minCoins[i] will be storing the minimum number of coins required for `i` value.
          // So minCoins[amount] will have a result
          int[] minCoins = new int[amount + 1];
  
          Arrays.fill(minCoins, MAX_VALUE);
          minCoins[0] = 0;
  
          Arrays.sort(coins);
  
          // Compute minimum coins required for all values from 1 to `amount`
          for (int i = 1; i <= amount; i++) {
  
              for (var coin : coins) {
                  // Go through all coins smaller or equals to `i`
                  if (i - coin >= 0) {
                      int subResult = minCoins[i - coin];
  
                      if (subResult != MAX_VALUE && subResult + 1 < minCoins[i]) {
                          minCoins[i] = subResult + 1;
                      }
                  }
              }
          }
  
          if (minCoins[amount] == MAX_VALUE) {
              return -1;
          }
  
          return minCoins[amount];
      }
  }
  