題目來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/coin-change
給定不同面額的硬幣 coins 和一個(gè)總金額 amount劈彪。編寫(xiě)一個(gè)函數(shù)來(lái)計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)竣蹦。如果沒(méi)有任何一種硬幣組合能組成總金額，返回 -1沧奴。
示例 1:
輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1
示例 2:
輸入: coins = [2], amount = 3
輸出: -1
說(shuō)明:
- 你可以認(rèn)為每種硬幣的數(shù)量是無(wú)限的痘括。
動(dòng)態(tài)規(guī)劃解法：
class Solution {
public int coinChange(int[] coins, int amount) {
if(coins.length == 0)
return -1;
if(amount <= 0)
return 0;
Arrays.sort(coins);
int[] dp = new int[amount+1];
dp[0] = -1;
for(int i = 1;i<=amount;i++){
int minCount = Integer.MAX_VALUE;
for(int j=coins.length-1;j>=0;j--){
int tmp = coins[j];
if(tmp <= i){
//取余數(shù)
int rem = i%tmp;
if(rem == 0){
//整除
minCount = Math.min(minCount,i/tmp);
}else{
//沒(méi)有整除
int count = i/tmp;
while(count > 0){
//取余數(shù)
rem = i - count*tmp;
if (dp[rem] != -1){
minCount = Math.min(minCount,dp[rem]+count);
}
count--;
}
}
}
}
if(minCount == Integer.MAX_VALUE){
dp[i] = -1;
}else{
dp[i] = minCount;
}
}
return dp[amount];
}
}
