322:零钱兑换
问题描述
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。
示例
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
输入: coins = [2], amount = 3
输出: -1
问题分析
这题我一开始当成贪心做了。因为在现实社会,我们的钱面值设置的是很巧妙的。选择贪心策略来找零钱是没有任何问题的,每次都找剩余里面的最大面值的,就一定能找开。
但是这题明显坑爹。。。钱币设置随心所欲,如果真的耿直得用贪心策略只会得到WA。
我想到了用DFS穷举所有的组合,发现合适的组合就返回,期间选择贪心策略,先从大的开始找,不成再换小的。(too simple)
对于 [1,7,10] 这种用例,比如要找14,按照贪心思路 10 + 1 + 1 + 1 + 1 会比 7 + 7 更早找到。所以还是要遍历完所有的可能来找到一个最小值。(Timeout)(方法一)
我们要考虑如何剪枝。不剪枝剪枝太慢了。剪枝的思路是:如果当前搜索的方式已经明显的比已经找到的方式要大,则直接剪枝。体现在for循环的i+count < ans中。(剪枝)
再次提速:自信点,贪心策略,每次都加最大的能加的值。(提速)(方法二)
上一下大佬的思路:
在探寻DFS时,观察写好的代码,突然发现这题既然可以用递归来做,那么必然可以转成动态规划。因为这个问题是拥有最优子结构性质的。
能看懂不?看不懂的话看我的白话文:
我们用一个dp
数组存储某个remains
,即剩余零钱需要的最少硬币数。
所以说我们得到一个remains
后,只需要查表就能解决剩余零钱为remains
时需要的最少硬币数。如果查不出来,没关系,我们可以算出来,只要设置好递归出口。
so,只要我们解决了remains
, 就能解决dp[amount]
。 因为dp[amount] = dp[remains]+1
, 而remains
等于什么呢?remains
等于amount-当前选择的coin
。
我们的coins有很多coin,所以我们要枚举所有的coin来得到一个最小值。(方法三,记忆型dp)
由于记忆型dp
还是要有递归调用栈,所以我们尝试把它改为递推型的dp
。
我们首先把dp
被最大值(可以说是一个不可达的值)充满。此时,dp[amount]
依然代表了对于amount
来说需要的最少硬币数。so,有的同学看到这里,非常机灵的指出来:为什么把dp
用最大值充满呢?因为这代表了一个不可达的值。我们在对dp
进行写值操作时,是尽力求出所有能组成它的最小值,既然是最小值,就要把它自己设置为一个不可达的值,这样才有办法与计算出来的值进行比较。
OK,那为什么dp[0]
要设置为0
呢?这样做是因为amount
等于0
时确实应该返回0
. 我们的dp
被最大值充满跟dp[0]
设置为0
没有任何关系。正如上面所说,被最大值充满是因为比较。(方法四)
方法一
Java版
class Solution1 {
int ans = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) {
dfs(coins, amount, 0, 0);
return ans==Integer.MAX_VALUE?-1:ans;
}
private void dfs(int[] coins, int amount, int count, int curIndex){
if(curIndex == coins.length){
return;
}
for(; amount >= 0 && ans > count; amount-=coins[curIndex],count++){
dfs(coins, amount, count, curIndex+1);
if(amount < coins[curIndex]){
break;
}
}
if(amount == 0){
ans = Math.min(ans,count);
}
}
}
方法二
Java版
class Solution2 {
int ans = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) {
Arrays.sort(coins);
int[] reversedSort = new int[coins.length];
for(int i = 0; i < coins.length; i++) reversedSort[i] = coins[coins.length-i-1];
dfs(reversedSort, amount, 0, 0);
return ans==Integer.MAX_VALUE?-1:ans;
}
private void dfs(int[] coins, int amount, int count, int curIndex){
if(amount == 0){
ans = Math.min(ans,count);
}
if(curIndex == coins.length){
return;
}
for(int i = amount/coins[curIndex]; i >= 0 && i+count < ans; i--){
dfs(coins, amount-i*coins[curIndex], count+i, curIndex+1);
}
}
}
方法三
Java版
class Solution {
public int coinChange(int[] coins, int amount) {
if(amount == 0){
return 0;
}
return getCoins(coins, amount, new int[amount]);
}
private int getCoins(int[] coins, int remains, int[] dp){
if(remains == 0){
return 0;
}else if(remains < 0){
return -1;
}
if(dp[remains-1] != 0){ // 记忆化技术
return dp[remains-1];
}
int min = Integer.MAX_VALUE;
for(int coin: coins){
int res = getCoins(coins, remains-coin, dp);
if(res > -1){
min = Math.min(min,res+1);
}
}
dp[remains-1] = min == Integer.MAX_VALUE?-1:min;
return dp[remains-1];
}
}
方法四
Java版
public class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
上一篇: 落枕的症状 落枕与颈型颈椎病的区别