题目： 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1: 输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 示例 2: 输入: coins = [2], amount = 3 输出: -1思路： 设dp[i]表示凑成总金额为i所需的最小硬币数。 那么凑成金额 i 的方法只有 dp[i - coins[j]] + 一个金额为coins[j]的硬币。 所以推导公式为： dp[i] = min(dp[i-coins[j]] + 1)
代码：
class Solution { public: int coinChange(vector<int>& coins, int amount) { sort(coins.begin(), coins.end()); int len = coins.size(); int dp[amount+1]; memset(dp,-1,sizeof(dp)); dp[0] = 0; for(int i=1;i<=amount;i++) { int mini = 999999999; for(int j=0;j<len && coins[j]<=i;j++) { if(dp[i-coins[j]] >= 0) mini = min(mini, dp[i-coins[j]]+1); } if(mini < 999999999) dp[i] = mini; } return dp[amount]; } };