322：零钱兑换

问题描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例

输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1

输入: coins = [2], amount = 3
输出: -1

问题分析

这题我一开始当成贪心做了。因为在现实社会，我们的钱面值设置的是很巧妙的。选择贪心策略来找零钱是没有任何问题的，每次都找剩余里面的最大面值的，就一定能找开。
但是这题明显坑爹。。。钱币设置随心所欲，如果真的耿直得用贪心策略只会得到WA。

我想到了用DFS穷举所有的组合，发现合适的组合就返回，期间选择贪心策略，先从大的开始找，不成再换小的。(too simple)
对于 [1,7,10] 这种用例，比如要找14，按照贪心思路 10 + 1 + 1 + 1 + 1 会比 7 + 7 更早找到。所以还是要遍历完所有的可能来找到一个最小值。(Timeout)(方法一)
我们要考虑如何剪枝。不剪枝剪枝太慢了。剪枝的思路是：如果当前搜索的方式已经明显的比已经找到的方式要大，则直接剪枝。体现在for循环的i+count < ans中。(剪枝)
再次提速：自信点，贪心策略，每次都加最大的能加的值。(提速)（方法二）
上一下大佬的思路：

在探寻DFS时，观察写好的代码，突然发现这题既然可以用递归来做，那么必然可以转成动态规划。因为这个问题是拥有最优子结构性质的。

能看懂不？看不懂的话看我的白话文：
我们用一个dp数组存储某个remains，即剩余零钱需要的最少硬币数。
所以说我们得到一个remains后，只需要查表就能解决剩余零钱为remains时需要的最少硬币数。如果查不出来，没关系，我们可以算出来，只要设置好递归出口。
so，只要我们解决了remains, 就能解决dp[amount]。 因为dp[amount] = dp[remains]+1， 而remains等于什么呢？remains等于amount-当前选择的coin。
我们的coins有很多coin，所以我们要枚举所有的coin来得到一个最小值。(方法三，记忆型dp)

由于记忆型dp还是要有递归调用栈，所以我们尝试把它改为递推型的dp。
我们首先把dp被最大值(可以说是一个不可达的值)充满。此时，dp[amount]依然代表了对于amount来说需要的最少硬币数。so,有的同学看到这里，非常机灵的指出来：为什么把dp用最大值充满呢？因为这代表了一个不可达的值。我们在对dp进行写值操作时，是尽力求出所有能组成它的最小值，既然是最小值，就要把它自己设置为一个不可达的值，这样才有办法与计算出来的值进行比较。
OK，那为什么dp[0]要设置为0呢？这样做是因为amount等于0时确实应该返回0. 我们的dp被最大值充满跟dp[0]设置为0没有任何关系。正如上面所说，被最大值充满是因为比较。(方法四)

方法一

Java版

class Solution1 {
    int ans = Integer.MAX_VALUE;
    public int coinChange(int[] coins, int amount) {
        dfs(coins, amount, 0, 0);
        return ans==Integer.MAX_VALUE?-1:ans;
    }
    private void dfs(int[] coins, int amount, int count, int curIndex){
        if(curIndex == coins.length){
            return;
        }
        for(; amount >= 0 && ans > count; amount-=coins[curIndex],count++){
            dfs(coins, amount, count, curIndex+1);
            if(amount < coins[curIndex]){
                break;
            }
        }
        if(amount == 0){
            ans = Math.min(ans,count);
        }
    }
}

方法二

Java版

class Solution2 {
    int ans = Integer.MAX_VALUE;
    public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        int[] reversedSort = new int[coins.length];
        for(int i = 0; i < coins.length; i++) reversedSort[i] = coins[coins.length-i-1];
        dfs(reversedSort, amount, 0, 0);
        return ans==Integer.MAX_VALUE?-1:ans;
    }
    private void dfs(int[] coins, int amount, int count, int curIndex){
        if(amount == 0){
            ans = Math.min(ans,count);
        }
        if(curIndex == coins.length){
            return;
        }
        for(int i = amount/coins[curIndex]; i >= 0 && i+count < ans; i--){
            dfs(coins, amount-i*coins[curIndex], count+i, curIndex+1);
        }
    }
}

方法三

Java版

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount == 0){
            return 0;
        }
        return getCoins(coins, amount, new int[amount]);
    }
    private int getCoins(int[] coins, int remains, int[] dp){
        if(remains == 0){
            return 0;
        }else if(remains < 0){
            return -1;
        }
        if(dp[remains-1] != 0){ // 记忆化技术
            return dp[remains-1];
        }
        int min = Integer.MAX_VALUE;
        for(int coin: coins){
            int res = getCoins(coins, remains-coin, dp);
            if(res > -1){
                min = Math.min(min,res+1);
            }
        }
        dp[remains-1] = min == Integer.MAX_VALUE?-1:min;
        return dp[remains-1];
    }
}

方法四

Java版

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