算法-回溯法/动态规划-零钱兑换

我会带着你远行 2023-02-12 11:22 45阅读 0赞

# 算法-回溯法/动态规划-零钱兑换 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/coin-change/

## 1.2 题目描述 ##

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

示例 1:

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

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

说明:  
你可以认为每种硬币的数量是无限的。

# 2 回溯法 #

## 2.1 思路 ##

首先将零钱从小到大排序，然后贪心地优先放面额大的零钱，直到超过目标值就回溯；或等于目标值，就比较当前零钱总数和最小值，如果更小就设为最小值，然后继续回溯。

## 2.2 代码 ##

class Solution { 
        public int coinChange(int[] coins, int amount) { 
            if(coins == null || coins.length == 0){ 
                return -1;
            }
            Arrays.sort(coins);
            return backtrack(coins, amount, 0, 0, coins.length - 1);
        }
    
        int min = Integer.MAX_VALUE;
    
        private int backtrack(int[] coins, int amount, int count, int sum, int max){ 
            if(sum > amount){ 
                // 结束条件
                return -1;
            }
            if(sum == amount){ 
                // 结束条件
                return count;
            }
            for(int i = max; i >= 0; i--){ 
                // 选择
                sum += coins[i];
                int result = backtrack(coins, amount, count + 1, sum, i);
                if(result > -1){ 
                    if(result < min){ 
                        min = result;
                    }
                }
                sum -= coins[i];
            }
            if(min == Integer.MAX_VALUE){ 
                return -1;
            }else{ 
                return min;
            }
        }
    }

## 2.3 时间复杂度 ##

![在这里插入图片描述][20200525221418702.png]  
时间复杂度太高，直接崩了

# 3 回溯法-剪枝 #

## 3.1 思路 ##

前面回溯法，相当于穷举所有组合，所有超时也是在情理之中。

但由于可能出现以下情况：  
对于这个测试用例

[13,12,11,9,61]
    33

优先找到：  
13 13 6 1  
然后可以找到  
13 12 6 1 1  
还可以找到  
13 11 9（最优解）

这说明，我们必须递归完这些解，否则可能无法找到全局最优解！

但是我们还是用了剪枝思想，见代码注释中的`k + cnt < res`。

## 3.2 代码 ##

class Solution { 
        private int min = Integer.MAX_VALUE;
    
        public int coinChange(int[] coins, int amount) { 
            if(coins == null || coins.length == 0){ 
                return -1;
            }
            Arrays.sort(coins);
            backtrack(coins, amount, 0, coins.length - 1);
            return min == Integer.MAX_VALUE ? -1 : min;
        }
        
        private void backtrack(int[] coins, int amount, int count, int max){ 
            if(amount == 0){ 
                // 结束条件
                min = Math.min(min, count);
                return;
            }
    
            if(max < 0){ 
                // 结束条件
                return;
            }
    
            // k + count < min是剪枝关键
            // 考虑 k + count == min，此时已经不需要再继续查找，因为更小面额肯定需要的数量更多，而相等数量的组合已经有了
            // 考虑 k + count > min，此时也已经不需要再继续查找，更小面额组合钞票数肯定更大于当前 k + count
    		
    		// 这里的循环是从取最多当前最大面值的钞票开始算
    		// k--表示下次少取一张当前最大面值的钞票开始算
            for(int k = amount / coins[max]; k >= 0 && (k + count < min) ; k--){ 
                backtrack(coins, amount - k * coins[max], count + k, max - 1);
            }
        }
    }

## 3.3 时间复杂度 ##

![在这里插入图片描述][20200526000346153.png]  
这次好很多！

# 4 动态规划 #

## 4.1 思路 ##

设dp\[i\]表示金额i的最小硬币个数，则

dp[i] = Math.min(dp[i-coins[0]] + 1, dp[i-coins[2]] + 1,...,dp[i-coins[n-1]] + 1);

因为金额 i 肯定是由coins\[0->n-1\]中的某一个硬币，和其他硬币组成。

那么我们只需要找到金额时使用最小的硬币个数的那个。

## 4.2 代码 ##

class Solution { 
        private int min = Integer.MAX_VALUE;
    
        public int coinChange(int[] coins, int amount) { 
            if(coins == null || coins.length == 0 || amount < 0){ 
                return -1;
            }
            if(amount == 0){ 
                return 0;
            }
    
            // 将硬币从小到大排序，当目标金额小于某个硬币面值时可直接排除大面额硬币
            Arrays.sort(coins);
    
            // 设dp[i]表示金额i的最小硬币个数
            // 则dp[i] = Math.min(dp[i-coins[0]] + 1, dp[i-coins[2]] + 1,...,dp[i-coins[n-1]] + 1);
            int[] dp = new int[amount + 1];
            dp[0] = 0;
            // 记录用到的最大硬币下标
            int max = coins.length - 1;
            // 更新用到的最大硬币下标，对一个硬币刚好能组成的金额进行dp[i]初始化为1
            for(int i = 0; i < coins.length; i++){ 
                if(amount == coins[i]){ 
                	// 如果目标金额刚好等于某个硬币面值，则直接由1个该硬币组成
                    return 1;
                }
                if(coins[i] > amount){ 
                	// 当前硬币 i 的面额大于目标金额，
                	// 那最大取值的硬币 最多是 硬币 i - 1；
                    max = i - 1;
                    break;
                }
                dp[coins[i]] = 1;
            }
            // 从1到amout开始动态规划过程
            for(int i = 1; i <= amount; i++){ 
                // 该金额对应的最小硬币个数
                int min = Integer.MAX_VALUE;
                // 遍历硬币，找到该金额使用的最小硬币数
                for(int j = 0; j <= max; j++){ 
                    if(coins[j] > i){ 
                        // 如果硬币面额比当前金额大，就停止当前趟查找最小硬币个数
                        break;
                    }
                    int tmp = dp[i-coins[j]];
                    if(tmp == -1){ 
                        // 该金额构成肯定不包含当前硬币
                        continue;
                    }
                    min = Math.min(min, tmp);
                }
                // min + 1 表示要加上一个硬币组成当前金额
                dp[i] = min == Integer.MAX_VALUE? -1 : (min + 1); 
            }
            return dp[amount];
        }
    }

## 4.3 时间复杂度 ##

![在这里插入图片描述][20200526102942383.png]

## 4.4 空间复杂度 ##

O(amount)

# 参考文档 #

*  [【零钱兑换】贪心 + dfs = 8ms][_ dfs _ 8ms]

[20200525221418702.png]: https://img-blog.csdnimg.cn/20200525221418702.png
[20200526000346153.png]: https://img-blog.csdnimg.cn/20200526000346153.png
[20200526102942383.png]: https://img-blog.csdnimg.cn/20200526102942383.png
[_ dfs _ 8ms]: https://leetcode-cn.com/problems/coin-change/solution/322-by-ikaruga/