Coin Change

Coin Change
You are given coins of different denominations and a total amount of money amount. 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.

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

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

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

题目的意思是给定一些不同面值的硬币和一个数值，写一个方法来判断是否能用现有的硬币组成给定的数值。假设每个面值的硬币都有无限个，如果可以组成给定的数值，就返回最少硬币的个数，否则返回-1。

这道题属于动态规划的问题，如果不用动态规划在leetcode上也可以ac，但是速度比较慢。用哈希表记录一个差值，就是给定的数值amount > coins[i]时，每遍历完一遍都更新哈希表，知道找到结果。代码如下：

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount == 0) return 0;
        Arrays.sort(coins);
        int result = 1;
        HashSet<Integer> helper = new HashSet<Integer>();
        for(int i = 0; i < coins.length; i++) {
            if(coins[i] == amount) {
                return result;
            } else if(amount > coins[i]) {
                helper.add(amount - coins[i]);
            }
        }
        boolean flag = true;
        while(flag) {
            HashSet<Integer> newset = new HashSet<Integer>();
            result ++;
            for(int newAmount : helper)
                for(int coin : coins) {
                    if(newAmount == coin) {
                        return result;
                    } else if(newAmount > coin) {
                        if(newAmount - coin >= coins[0]) {
                            newset.add(newAmount - coin);
                        }
                    } else {
                        break;
                    }
                } 
            if(newset.isEmpty()) {
                flag = false;
            } else {
                helper = newset;
            }
        }
        return -1;
    }
}

接下来我们动态规划的方法做，我们用一个数组dp[]来表示从0到amount，如果coins[i] = x时,x属于0到amount，dp[x] = 1; 当 x > coins[i]时，我们要查看之前是否已经计算出总数为x-coins[i]的情况，如果已经计算出，dp[x] = Math.min(dp[i - coins[j]] + 1, dp[x])；如果没有计算出就继续查找。细节的地方需要注意，比如数组的初始化等，代码如下：

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