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.

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

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

一刷
题解：
方法1: 用dynamic programming, int[] dp保存0-amout的结果。
但是这样会造成array out of boundary, 原因是空间复杂度可以达到O(amount)

public static int coinChange(int[] coins, int amount) {
        if(amount==0) return 0;
     
        int[] dp = new int [amount+1];
        dp[0]=0; // do not need any coin to get 0 amount
        for(int i=1;i<=amount; i++)
            dp[i]= Integer.MAX_VALUE;
     
        for(int i=0; i<=amount; i++){
            for(int coin: coins){
                if(i+coin <=amount){
                    if(dp[i]!=Integer.MAX_VALUE){
                        dp[i+coin] = Math.min(dp[i+coin], dp[i]+1);
                    }
                }
            }
        }
     
        if(dp[amount] >= Integer.MAX_VALUE)
            return -1;
     
        return dp[amount];
    }

方法2: Breath First Search (BFS)
amountQueue存储当前的coin sum up的值，step存储对应的硬币数目。
但是会出现超时的问题

public static int coinChange(int[] coins, int amount) {
        if(amount == 0) return 0;
        
        LinkedList<Integer> amountQueue = new LinkedList<Integer>();
        LinkedList<Integer> stepQueue = new LinkedList<Integer>();
        
        amountQueue.offer(0);//attach to the tail
        stepQueue.offer(0);
        
        while(amountQueue.size()>0){
            int temp = amountQueue.poll();
            int step = stepQueue.poll();
            
            if(temp == amount) return step;
            
            for(int coin : coins){
                if(temp<=amount){
                    if(!amountQueue.contains(temp+coin)){
                        amountQueue.offer(temp+coin);
                        stepQueue.offer(step+1);
                    }
                }
            }
        }
        
        return -1;
    }

二刷
用map替代dp数组做dp

class Solution {
    Map<Integer, Integer> amountDict = new HashMap<>();
    public int coinChange(int[] coins, int amount) {
        if(amount == 0) return 0;
        if(amountDict.containsKey(amount)) return amountDict.get(amount);
        int n = amount + 1;
        for(int coin : coins){
            int curr = 0;
            if(amount>=coin){
                int next = coinChange(coins, amount-coin);
                if(next>=0) curr = next+1;
            }
            if(curr>0) n = Math.min(n, curr);
        }
        
        int finalCount = (n==amount+1)? -1:n;
        amountDict.put(amount, finalCount);
        return finalCount;
    }
}