欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

322:零钱兑换

程序员文章站 2022-07-08 09:44:03
...

问题描述

给定不同面额的硬币 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中。(剪枝)
再次提速:自信点,贪心策略,每次都加最大的能加的值。(提速)(方法二)
上一下大佬的思路:
322:零钱兑换
在探寻DFS时,观察写好的代码,突然发现这题既然可以用递归来做,那么必然可以转成动态规划。因为这个问题是拥有最优子结构性质的。
322:零钱兑换
能看懂不?看不懂的话看我的白话文:
我们用一个dp数组存储某个remains,即剩余零钱需要的最少硬币数
所以说我们得到一个remains后,只需要查表就能解决剩余零钱为remains时需要的最少硬币数。如果查不出来,没关系,我们可以算出来,只要设置好递归出口。
so,只要我们解决了remains, 就能解决dp[amount]。 因为dp[amount] = dp[remains]+1, 而remains等于什么呢?remains等于amount-当前选择的coin
我们的coins有很多coin,所以我们要枚举所有的coin来得到一个最小值。(方法三,记忆型dp)

322:零钱兑换
322:零钱兑换
由于记忆型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];
  }
}