Coin Change

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.

解决方案： 利用动态规划来做会比较简单，设am[i] 在给定面额下，amount=I时的最小硬币个数， 令am[0]=0，am[i]=min{ am[i - coin[ j ] ] , 正无穷}。 最后当am[ amount ]=正无穷时，说明不能组合出给定的amount，return-1； 否则，return am[ amount ]. 代码如下： class Solution { public: int coinChange(vector<int>& coins, int amount) { int *am=new int[amount+1]; int len=coins.size(); int i,j,temp,result; am[0]=0; for(i=1;i<=amount;i++){ temp=INT_MAX; for(j=0;j<len;j++){ if((i-coins[j])>=0){ temp=min(temp, am[i-coins[j]]); } } am[i]=(temp==INT_MAX)?INT_MAX:(temp+1); } if(am[amount]==INT_MAX) result=-1; else result=am[amount]; delete []am; return result; } int min(int x, int y){ return x<=y?x:y; } /* int max(int x,int y){ return x>=y?x:y; } */ };