給定不同面額的硬幣 coins 和一個(gè)總金額 amount感局。編寫一個(gè)函數(shù)來計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)扫茅。如果沒有任何一種硬幣組合能組成總金額，返回 -1逗嫡。
示例 1:
輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1
示例 2:輸入: coins = [2], amount = 3
輸出: -1
說明:
你可以認(rèn)為每種硬幣的數(shù)量是無限的青自。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/coin-change
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)驱证，非商業(yè)轉(zhuǎn)載請注明出處延窜。
動(dòng)態(tài)規(guī)劃
class Solution {
/**
* 動(dòng)態(tài)規(guī)劃
* 1. 狀態(tài)定義：
* f(i)=湊成總金額i所需的最少的硬幣個(gè)數(shù)
* 2. 狀態(tài)轉(zhuǎn)移方程：
* f(i)=min{f(0), f(1), ..., f(i-1)} + 1
*
* @param coins
* @param amount
* @return
*/
public int coinChange(int[] coins, int amount) {
if (amount == 0) {
return 0;
}
int[] moneyCount = new int[amount + 1]; // index:總金額, value:最少的硬幣個(gè)數(shù)
for (int i = 1; i <= amount; i++) {
Integer min = null;
for (int coin : coins) {
if (i - coin < 0 || moneyCount[i - coin] == -1) {
continue;
}
if (min == null || min > moneyCount[i - coin]) {
min = moneyCount[i - coin];
}
}
moneyCount[i] = min != null ? min + 1 : -1;
}
return moneyCount[amount];
}
}
運(yùn)行效率
