硬币兑换

墨蓝 2023-02-20 07:12 108阅读 0赞

1，原文地址

[https://leetcode-cn.com/problems/coin-change/][https_leetcode-cn.com_problems_coin-change]

2，题目

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

**示例 1:**

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

**示例 2:**

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

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

3，解法

class Solution {
    
        private int ans = Integer.MAX_VALUE;
    
        public int coinChange(int[] coins, int amount) {
            //先将硬币排序，从小到大排序
            Arrays.sort(coins);
            //递归查询可能的排列组合，由于硬币是从小到大，所以，要从硬币数组的末尾往前取
            /**
             * 思路：
             * 1，用相对大的那个硬币，去匹配目标钱数
             * 2，还需要考虑特殊情况，比如 7+7 = 14
             */
            coinsChange(coins.length -1,coins,0,amount);
    
            //返回值
            return ans == Integer.MAX_VALUE?-1:ans;
        }
    
        /**
         *
         * @param index 硬币数组的索引
         * @param coins 硬币组合
         * @param count 需要的硬币数量
         * @param needAmount 还需要匹配的钱
         */
        private void coinsChange(int index, int[] coins, int count, int needAmount) {
            if(needAmount == 0){//当没有需要匹配的钱了
                ans = Math.min(count,ans);
                return;
            }
    
            if(index < 0){//没有硬币可用了
                return;
            }
    
            int k = needAmount / coins[index];//为满足匹配，需要当前几个硬币
    
            //进入下一层，
            // count+i < ans,是为了剪枝，
            // 即ans存储某次符合条件的硬币数量，
            //      如果后面某次的数量已经大于或者等于这个值时，就没必要进行后续的匹配了。
            for(int i = k;i>= 0 && count +i < ans;i--){
                coinsChange(index-1,coins,count+i,needAmount - i * coins[index]);
            }
        }
    }

[https_leetcode-cn.com_problems_coin-change]: https://leetcode-cn.com/problems/coin-change/