题目描述：

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

动态规划 c++代码：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        int dp[amount+1];//dp[i]表示凑成i需要的最少张数
        dp[0]=0; //凑0需要0个硬币
        for(int i=1;i<=amount;i++)dp[i]=amount+1; //初始化1～amount需要的硬币数为amount+1(因为后面要求最小值，所以先初始化为最大值)
        for(int i=1;i<=amount;i++){
            for(int j=0;j<n;j++){
                if(coins[j]<=i) //只有当前硬币小于要凑的面额时，才考虑是否使用当前硬币，若大于直接跳过
                dp[i]=min(dp[i],dp[i-coins[j]]+1); //选择使用coins[i],或不选择使用
            }
        }
        if(dp[amount]>amount)return -1;
        return dp[amount];
    }
};

要凑的数额为amount，定义dp[i]为凑数额 i 需要的最少硬币数。

对于每个i，从coins中选取硬币，如果coins[j]小于等于要凑的数i，则可以选择coins[j]或不选择：dp[i] = min(dp[i],dp[i-coins[j]]+1)

最后返回dp[amount]，即为凑amount需要的最少硬币数。若dp[amount]
大于amount，说明凑失败了，return -1。

注意初始化所有的dp[i]为amount+1（或者更大的数），因为要求dp[i]的最小值，所以先初始化它们为极大值。dp[0]=0，凑0不需要硬币。