力扣322——零钱兑换
- 2020 年 2 月 19 日
- 筆記
这道题主要涉及动态规划，利用这个，就能很好解决这个问题。
原题
给定不同面额的硬币 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 提交，有种又快又好的感觉。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题主要利用动态规划就可以解决，优化的时候需要注意边界条件，从大到小取值，在时间复杂度上能更加优化。
