DFS的灵活应用二：零钱兑换

最新推荐文章于 2023-05-21 13:11:09 发布

Healist

最新推荐文章于 2023-05-21 13:11:09 发布

阅读量361

点赞数

分类专栏：解题 java 文章标签： leetcode 算法 dfs

本文链接：https://blog.csdn.net/Healist/article/details/105106206

版权

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

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

思路：数组整体降序排列，然后dfs深度遍历，每次都挑额度大的先拿，以目前金额能拿多少就拿多少，拿多了就回溯走其他情况，相当于要把全部情况走一遍找到最小次数

代码设计中比较好的点：

有的回溯是要在递归的后面做额外补偿，此处的回溯是基于当前情况的for循环遍历
剪枝逻辑（当前硬币金额拿的个数+历史已拿个数<目前已知最少次数），相当于避免了很多无用递归执行

代码如下：

public class Solution {
   

    class Times {
   

        public Times(int bestTimes) {
   
            this.bestTimes = bestTimes;
        }

        private int bestTimes;


        public int getBestTimes() {
   
            return bestTimes;
        }

        private void compareMin(int num) {