已知不同面值的钞票，求如何用最少数量的钞票组成某个金额，求可以使用的最少钞票数量。如果任意数量的已知面值钞票都无法组成该金额，则返回-1
例如：
钞票面值：[1,2,5]; 金额：11=5+5+1；需要3张。
钞票面值：[2]；金额：3；无法组成，返回-1。
钞票面值：[1,2,5,7,10]；金额：14=7+7，需要2张。

#include <vector>
class Solution
{
public:
 Solution(){}
 ~Solution(){}
 int coinsChange(std::vector<int>& coins, int amount)
 {
  std::vector<int> dp;
  for (int i = 0; i <=amount; i++)
  {
   dp.push_back(-1);
  }
  dp[0] = 0;
  for (int i = 1; i <=amount; i++)
  {
   for (int j = 0; j < coins.size(); j++)
   {
    if (i-coins[j]>=0&&dp[i-coins[j]]!=-1)       
     //i-coins[j]>=0的等号不可忽略，等号存在时相当于在初始化coins向量的dp值为1
    {
     if (dp[i]==-1||dp[i]>dp[i-coins[j]]+1)
     {
      dp[i] = dp[i - coins[j]] + 1;
     }
    }
   }
  }
  return dp[amount];
 }
};
int main()
{
 Solution solve;
 std::vector<int> coins;
 coins.push_back(1);
 coins.push_back(2);
 coins.push_back(5);
 coins.push_back(7);
 coins.push_back(10);
 for (int i = 1; i <=14; i++)
 {
  printf("dp[%d]=%d\n",i, solve.coinsChange(coins, i));
 }
 return 0;
}

运行结果为：

dp[1]=1
dp[2]=1
dp[3]=2
dp[4]=2
dp[5]=1
dp[6]=2
dp[7]=1
dp[8]=2
dp[9]=2
dp[10]=1
dp[11]=2
dp[12]=2
dp[13]=3
dp[14]=2