題目地址： https://leetcode-cn.com/problems/coin-change/
題目描述：
給定不同面額的硬幣 coins 和一個(gè)總金額 amount。編寫(xiě)一個(gè)函數(shù)來(lái)計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)臭杰。如果沒(méi)有任何一種硬幣組合能組成總金額曹动，返回 -1。
你可以認(rèn)為每種硬幣的數(shù)量是無(wú)限的饰恕。
示例 1： 輸入：coins = [1, 2, 5], amount = 11 輸出：3 解釋：11 = 5 + 5 + 1
示例 2： 輸入：coins = [2], amount = 3 輸出：-1
示例 3： 輸入：coins = [1], amount = 0 輸出：0
示例 4： 輸入：coins = [1], amount = 1 輸出：1
示例 5： 輸入：coins = [1], amount = 2 輸出：2
提示：
1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4
參考代碼：
lass Solution {
public:
int coinChange(vector<int>& coins, int amount) {
//dp[j] = d[j] dp[j-coint[i]] +1
vector<int> dp = vector<int>(amount+1,INT_MAX);
dp[0] = 0;
for (int i = 0; i<coins.size(); i++) {
for (int j = coins[i]; j<=amount;j++) {
if (j>=coins[i] && dp[j-coins[i]] != INT_MAX) {
dp[j] = min(dp[j],dp[j-coins[i]]+1);
}
}
}
if (dp[amount] == INT_MAX) {
return -1;
}
return dp[amount];
}
};
