Leetcode322.零钱兑换

思路：
一开始想起来的就是给现有的零钱进行排序，然后选取最大面值的零钱，进行回溯，找到就立即退出，这样的做法没有考虑到1，7，10 amount = 14这种情况，10，1，1，1，1与7，7肯定是最少两个硬币。如果说遍历所有的情况，不提前退出，会出现超时的情况。那么回溯的时候不用每次都只减一个coins[i]，而是每次减个amount/coins[i]coins[i]，这样的话也不行，没有考虑到2，4，5 amount= 11这种情况，因为一次性减25的话，由于找不到1，结果就是-1，其实结果应该是2，4，5，结果为3
所以这道题用dfs是需要花费些心思的，还需要进行剪枝来防止超时的发生。

class Solution {
    int min = Integer.MAX_VALUE;
    public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        helper(coins,amount,0,coins.length-1);
        if(min == Integer.MAX_VALUE){
            return -1;
        }else{
            return min;
        }
    }
    public void helper(int[] coins,int amount,int count,int index){
        if(amount == 0){
            min = Math.min(min,count);
            return;
        }
        if(index < 0) return;
        for(int k = amount/coins[index];k >= 0 && k + count < min;k--){//剪枝条件
                helper(coins,amount-k*coins[index],count+k,index-1);
            }
    }
}

第二种做法就是使用动态规划方法
f(i)为为实现为i的钱数需要多少硬币,总共的硬币面额为2，3，4
f(1) = min(f(1-2),f(1-3),f(1-4))+1;
f(2)= min(f(2-2),f(2-3),f(2-4))+1;
f(3)=min(f(3-2),f(3-3),f(3-4))+1;
.
.
.
f(i) = min(f(i-2),f(i-3),f(i-4))+1;

class Solution {
    int min = Integer.MAX_VALUE;
    public int coinChange(int[] coins, int amount) {
       // Arrays.sort(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++){
                if(i >= coins[j]){
                    dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
                }  
            }
        }
        return dp[amount] == amount+1? -1:dp[amount];
    }

}