找零钱(DP或BFS)(leetcode322)

（想不到到头来还是捡起了算法，当初大二离开ACM就是因为觉得算法太无聊，开发有意思。现在感觉开发没意思了O.O

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.

这道题很容易想起用BFS做，但是直接使用的话内存会爆。

从上图可以看出有很多重复的情况，可以用一个数组来记忆访问情况，后续遇到同样的情况就不需要递归了，这样就可以通过。

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(coins==null||coins.length==0||amount<1)  return 0;
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        HashSet<Integer> visited = new HashSet<>();
        queue.add(amount);
        visited.add(amount);
        int count = 0;

        while(!queue.isEmpty()){
            int size = queue.size();
            while(size-- > 0){
                int curr = queue.removeFirst();
                if(curr==0) return count;
                if(curr<0)  continue;

                for (int coin : coins) {
                    int next = curr-coin;
                    if(next>=0&&!visited.contains(next)){
                        visited.add(next);
                        queue.add(next);
                    }
                }
            }   
            count++;
        }
        return -1;
    }
}

然后就是DP做法，DP[i]数组存的是当i块钱时，可以使用的最小钞票数量。

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(coins==null||coins.length==0)    return -1;
        if(amount==0){
            return 0;
        }
        // dp[i]代表i块钱在coins[]下的拼凑的最少钱数
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount+1);
        dp[0]=0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                int amountLeft = i-coins[j];
                if(amountLeft>=0){
                    dp[i] = Math.min(dp[i],dp[amountLeft]+1);
                }
            }
        }
        return dp[amount]==amount+1?-1:dp[amount];
    }
}