Problem

You are given coins of different denominations and a total amount of moneyamount. Write a function to compute 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.

Example 1:
coins =[1, 2, 5], amount =11
return3(11 = 5 + 5 + 1)

Example 2:
coins =[2], amount =3
return-1.

思路一（recursive）

• coinChange can be composed of smaller coinChange problem.

• if coins[i] is taken, coinChange(coins, amount) = 1 + coinChange(coins, amount - coins[i])

• and it can be optimized by memorization with a map or an array

class Solution {

    Map<Integer, Integer> map = new HashMap<>();

    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;

        if (map.containsKey(amount)) return map.get(amount);

        int result = amount + 1;
        for (int i = 0; i < coins.length; i++) {
            if (coins[i] > amount) continue;
            int subCoins = coinChange(coins, amount - coins[i]);
            if (subCoins < 0) continue;
            result = Math.min(result, 1 + subCoins);
        }
        result = result == amount + 1 ? -1 : result;
        map.put(amount, result);
        return result;
    }
}

思路二（iterative）

• we think in bottom-up manner. Suppose we have already computed all the minimum counts up tosum, what would be the minimum count forsum+1?

class Solution {
    public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i && dp[i - coins[j]] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], 1 + dp[i - coins[j]]);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}