題目
給定不同面額的硬幣 coins 和一個總金額 amount逛裤。編寫一個函數(shù)來計算可以湊成總金額所需的最少的硬幣個數(shù)。如果沒有任何一種硬幣組合能組成總金額，返回 -1叉谜。
示例 1:
輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1
示例 2:
輸入: coins = [2], amount = 3
輸出: -1
說明:
你可以認(rèn)為每種硬幣的數(shù)量是無限的陡蝇。
解析
思路一
思路二
思路三
代碼
public int CoinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];//初始化數(shù)組
for(int i = 0;i<=amount;i++){
dp[i] = -1;//最初所有的金額的最優(yōu)解均為-1（不可達(dá)到）
}
dp[0] = 0;//金額0的最優(yōu)解0 //遞推
for(int i = 1;i<=amount;i++){//循環(huán)各個面值痊臭，找到dp[i]的最優(yōu)解
for(int j = 0;j< coins.Length;j++){
if(i-coins[j]>=0&&dp[i-coins[j]]!=-1){
if(dp[i] == -1||dp[i]>dp[i-coins[j]]+1){
dp[i] = dp[i-coins[j]]+1; //遞推公式
}
}
}
}
return dp[amount];
}
