The Problem

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Check LeetCode link for more details and example input & output.

Dynamic Programming Solutions

A Top Down Approach

A Java solution.

  public int coinChange(int[] coins, int amount) {
      return coinChange(coins, amount, new HashMap<>());
  }

  int coinChange(int[] coins, int amount, Map<Integer, Integer> dp) {
      if (amount < 0) {
          return -1;
      }
      if (amount == 0) { // a base case & edge case
          return 0;
      }
      if (dp.get(amount) != null) {
          return dp.get(amount);
      }

      int min = amount + 1; // ā‘ 
      for (int i = 0; i < coins.length; i++) {
          int changes = 1 + coinChange(coins, amount - coins[i], dp);
          // `changes == 0` meaning the above `coinChange` call return `-1`,
          // no need to update `min` in this case
          if (changes != 0 && changes < min) {
              min = changes;
          }
      }
      // if `min` stays at its initial value, it means no answer for input `amount`
      if (min == amount + 1) {
          min = -1;
      }

      dp.put(amount, min);

      return min;
  }

For initial value of min, (line ā‘ ), amount + 1 is big enough. Because even if coin 1 exists, the maximum value of changes is amount.

A Bottom Up Approach

dp[i] = min(1 + dp[i - coins[0]], 1 + dp[i - coins[1]], 1 + dp[i - coins[2]], ...)

dp[i] is the answer of the sub problem ā€œiā€, where i is the input of the amount for this sub problem.

Base case is dp[0] = 0.

  public int coinChange(int[] coins, int amount) {
      // array length is `amount + 1`, since we are to calculate dp[amount]
      int[] dp = new int[amount + 1];
      // set initial value. why `amount + 1`, see comments above.
      Arrays.fill(dp, amount + 1);

      dp[0] = 0; // the base case and the edge case

      for (int i = 1; i <= amount; i++) {
          for (int j = 0; j < coins.length; j++) {
              int index = i - coins[j];
              // to avoid out-of-bound when index is negative
              if (index >= 0) { 
                  dp[i] = Math.min(dp[i], 1 + dp[index]);
              }
          }
      }

      // if it's still the initial value, return -1
      if (dp[amount] == amount + 1) {
          return -1;
      }

      return dp[amount];
  }

The time complexity is O(n*m), n is amount, m is number of coins.