給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額,返回 -1。
示例1:
輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1
示例2:
輸入: coins = [2], amount = 3
輸出: -1
說明:
你可以認為每種硬幣的數量是無限的。
分析
這題可以用貪心也可以用dp,這里使用dp方式,以示例1舉例,如下圖
有硬幣[1, 2, 5],想要組成11,那就需要先組成(11-1, 11-2, 11-5),即(10, 9, 6),括號內為或關系,就是說想要組成11,那就需要先組成10或9或6,這里用dp存儲組成x需要的硬幣個數,則dp[11]= min(dp[10], dp[9], dp[6])+1,依此類推,dp[10] = min(dp[10-1], dp[10-2], dp[10-5]) + 1,這是從上向下類推,基本上從上向下類推的規律都可以從下向上推導,具體可以看代碼啦。
代碼
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if (amount == 0) return 0;
// 如果沒有任何一種硬幣組合能組成總金額,返回 -1
const int fail_value = -1;
vector<int> dp(amount + 1, fail_value);
std::sort(coins.begin(), coins.end());
for (int i = 1; i <= amount; ++i) {
for (auto coin : coins) {
if (i == coin) {
dp[i] = 1;
break;
}
if (i < coin) {
break;
}
if (dp[i-coin] != fail_value) {
if (dp[i] == fail_value) {
dp[i] = dp[i-coin] + 1;
} else {
dp[i] = min(dp[i-coin] + 1, dp[i]);
}
}
}
}
return dp[amount];
}
};
如有任何問題,可以聯系喵大人 ,我會盡快回復噠!