You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1: coins = [1, 2, 5], amount = 11 return 3 (11 = 5 + 5 + 1)
Example 2: coins = [2], amount = 3 return -1.
Note: You may assume that you have an infinite number of each kind of coin.
s思路: 1. 看到這種題，就想到backtracking啊，recursive啊。 2. 但又不完全是，題目和以前的題目還是有差別。 3. 有點繁瑣，看了hint,需要用dp。可不是嗎？首先求最值，然后用coins的和得到給的一個target,那么組成的過程就是從元問題開始，一步一步的得到這個target的。這樣，就更要用dp了 4. 也就是說，下次看到這類題，還應該先想想dp. 5. 這個dp想明白了，也很簡單。從元問題開始，加上所有的硬幣，得到一個硬幣數，然后amount++,整個復雜度就是o(amount*number of coins) 6. 當然也可以在每個位置減去硬幣數
//方法１：dpclass Solution {public: int coinChange(vector<int>& coins, int amount) { // if(amount==0) return 0; sort(coins.begin(),coins.end()); //if(coins[0]>amount) return -1; vector<int> dp(amount+1,INT_MAX); dp[0]=0; for(int i=0;i<amount;i++){ for(int c:coins){ if(i>0&&dp[i]==INT_MAX||i+long(c)>amount) continue;//bug: dp[i+c]=min(dp[i+c],dp[i]+1); } } return dp[amount]==INT_MAX?-1:dp[amount]; }};//方法1.1：改進了dp，初值不用int_max,而用更嚴格的界限，即：最大值為amount+1,問題就簡單了！class Solution {public: int coinChange(vector<int>& coins, int amount) { // if(amount==0) return 0; vector<int> dp(amount+1,amount+1); dp[0]=0; for(int i=0;i<coins.size();i++){ for(int j=coins[i];j<=amount;j++){//bug:兩個for循環交換位置，就不用判斷是否前一個值不能有硬幣構成，這個確實妙，一般不容易看到！小ｔｒｉｃｋ dp[j]=min(dp[j],dp[j-coins[i]]+1); } } return dp[amount]==amount+1?-1:dp[amount]; }};新聞熱點
疑難解答
