coin_change.java

public static int coinChange(int[] coins, int amount, Map<Integer, Integer> map) {
    if (map.get(amount) != null) return map.get(amount);
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    int minimumCoin = Integer.MAX_VALUE;
    for (int coin : coins) {
      int remainder = amount - coin;
      int coinNeeded = coinChange(coins, remainder, map);
      map.put(remainder, coinNeeded);
      if (coinNeeded != -1) {
        minimumCoin = Math.min(minimumCoin, coinNeeded + 1);
      }
    }
    return minimumCoin == Integer.MAX_VALUE ? -1 : minimumCoin;
  }