15°

力扣322——零钱兑换

这道题主要涉及动态规划,利用这个,就能很好解决这个问题。

原题

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

示例 1:

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

示例 2:

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

说明:

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

原题url:https://leetcode-cn.com/problems/coin-change/

解题

求出所有可能

我们可以从小到大,求出由当前硬币,组成所有金额的最小数,这样最终就是最大金额所能组成的最小硬币数量。

这种方法核心思想就是记录所有中间状态的结果,如果在实际使用中,你的传入参数amount是不断变化的,那么用这种方法会比较方法,因为之前的结果可以被重复利用,这样也是一种优势。

现在我们来看看代码:

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 排序,升序
        Arrays.sort(coins);
    // 用来记录中间结果,各种金额所需要的硬币数量
    int[] result = new int[amount + 1];
    result[0] = 0;
    // 遍历所有可能的金额
    for (int currentAmount = 1; currentAmount <= amount; currentAmount++) {
        int minNum = Integer.MAX_VALUE;
        // 遍历所有硬币
        for (int j = 0; j < coins.length; j++) {
            // 当前金额已经比硬币的值小
            int remainAmount = currentAmount - coins[j];
            if (remainAmount < 0) {
                break;
            }

            // remainAmount无法由硬币组成
            if (result[remainAmount] == Integer.MAX_VALUE) {
                continue;
            }

            // 取更小的值
            minNum = Math.min(minNum, result[remainAmount] + 1);
        }

        result[currentAmount] = minNum;
    }

    return result[amount] == Integer.MAX_VALUE ? -1 : result[amount];
}

}

提交OK,执行用时:12 ms,内存消耗:36 MB,只超过了83.24%的 java 提交,看来还有优化的空间。

动态规划优化

倒不是说动态规划就一定比上面的方法更加优秀,只是也是一种思想,可以利用 dfs(深度优先搜索) 或者 bfs(广度优先搜索),我下面这种写法是 dfs,因为是一路进行到底之后,再去考虑其他情况的。(补充一点,如果使用 bfs 的话,可以借助队列来实现非递归的形式。)

所谓的优化,就是从硬币的使用上来说,从面值大的开始,并且从可以使用数量最大的开始。与此同时,我们也记录了最小使用数量,如果用当前面值最大的硬币并且使用最多时,依旧大于最小值,那么就不用继续查找了。

以上的优化,其实是和题目相关联,虽然不能用在其他的题目上,但也可以作为一种思想,值得我们借鉴和学习。

接下来我们看看代码:

class Solution {
    private int minCount = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) {
    // 排序
    Arrays.sort(coins);
    // 从大往小找
    helper(coins, coins.length - 1, 0, amount);
    return minCount == Integer.MAX_VALUE ? -1 : minCount;
}

private void helper(int[] coins, int coinIndex, int curCount, int amount) {
    if (coinIndex < 0) {
        return;
    }
    // 如果能整除,直接取完
    if (amount % coins[coinIndex] == 0) {
        minCount = Math.min(minCount, curCount + amount / coins[coinIndex]);
        return;
    }

    // 数量上也是从大往小找
    for (int i = amount / coins[coinIndex]; i >= 0; i--) {
        // 因为接下来至少还会用1个币
        if (curCount + i + 1 >= minCount) {
            break;
        }
        
        helper(coins, coinIndex - 1, curCount + i, amount - i * coins[coinIndex]);
    }
}

}

提交OK,执行用时:2 ms,内存消耗:34.7 MB,超过了100.00%的 java 提交,有种又快又好的感觉。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题主要利用动态规划就可以解决,优化的时候需要注意边界条件,从大到小取值,在时间复杂度上能更加优化。

有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。

https://death00.github.io/

公众号:健程之道

本文转载自博客园,原文链接:https://www.cnblogs.com/death00/p/12203376.html

全部评论: 0

    我有话说: