算法:322. Coin Change找零钱
2021/5/17 1:25:35
本文主要是介绍算法:322. Coin Change找零钱,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
322. Coin Change
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
Example 1:
Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3 Output: -1
Example 3:
Input: coins = [1], amount = 0 Output: 0
Example 4:
Input: coins = [1], amount = 1 Output: 1
Example 5:
Input: coins = [1], amount = 2 Output: 2
Constraints:
1 <= coins.length <= 12 1 <= coins[i] <= 231 - 1 0 <= amount <= 104
递归解法
#递归方法:#
这个想法是非常经典的动态编程:想想我们要采取的最后一步。假设我们已经找到了总结,以量的最佳方法a,那么对于最后一步,我们可以选择任何硬币型这给了我们一个余数r,其中r = a-coins[i]所有i的。对于每个余数,请执行与之前完全相同的过程,直到余数为0或小于0(表示无效的解决方案)。有了这个想法,剩下的唯一细节就是存储总和所需的最小数量的硬币,r这样我们就不需要一遍又一遍地重新计算它。
public class Solution { public int coinChange(int[] coins, int amount) { if(amount<1) return 0; return helper(coins, amount, new int[amount]); } private int helper(int[] coins, int rem, int[] count) { // rem: remaining coins after the last step; count[rem]: minimum number of coins to sum up to rem if(rem<0) return -1; // not valid if(rem==0) return 0; // completed if(count[rem-1] != 0) return count[rem-1]; // already computed, so reuse int min = Integer.MAX_VALUE; for(int coin : coins) { int res = helper(coins, rem-coin, count); if(res>=0 && res < min) min = 1+res; } count[rem-1] = (min==Integer.MAX_VALUE) ? -1 : min; return count[rem-1]; } }
参考
https://leetcode.com/problems/coin-change/discuss/77368/Java-Both-iterative-and-recursive-solutions-with-explanations
动态规划解法
迭代方法:#对于迭代解决方案,我们以自下而上的方式进行思考。假设我们已经计算出了所有的最小计数sum,那么最小计数将是sum+1多少?
public class Solution { public int coinChange(int[] coins, int amount) { if(amount<1) return 0; int[] dp = new int[amount+1]; int sum = 0; while(++sum<=amount) { int min = -1; for(int coin : coins) { if(sum >= coin && dp[sum-coin]!=-1) { int temp = dp[sum-coin]+1; min = min<0 ? temp : (temp < min ? temp : min); } } dp[sum] = min; } return dp[amount]; } }
这篇关于算法:322. Coin Change找零钱的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享