給定不同面額的硬幣 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ù)量是無限的。
分析
這題可以用貪心也可以用dp，這里使用dp方式，以示例1舉例，如下圖
有硬幣[1, 2, 5]，想要組成11，那就需要先組成(11-1, 11-2, 11-5)，即(10, 9, 6)，括號(hào)內(nèi)為或關(guān)系，就是說想要組成11，那就需要先組成10或9或6，這里用dp存儲(chǔ)組成x需要的硬幣個(gè)數(shù)，則dp[11]= min(dp[10], dp[9], dp[6])+1，依此類推，dp[10] = min(dp[10-1], dp[10-2], dp[10-5]) + 1，這是從上向下類推，基本上從上向下類推的規(guī)律都可以從下向上推導(dǎo)，具體可以看代碼啦。
代碼
class Solution {public:int coinChange(vector<int>& coins, int amount) {if (amount == 0) return 0;// 如果沒有任何一種硬幣組合能組成總金額，返回 -1const 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];}};
如有任何問題，可以聯(lián)系喵大人 ，我會(huì)盡快回復(fù)噠！