给你一个整数数组 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] <= 2(31) - 1

0 <= amount <= 10(4)

与完全平方数类似，我们需要依次减去对应的面额，来取最小值

注意范围的判断和不满足条件时-1的取值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int coinChange(vector<int> &coins, int amount) {
        vector<int> dp(amount + 1);
        int n = coins.size();
        for (int i = 1; i <= amount; i++) {
            int mid = INT_MAX;
            for (int j = 0; j < n; j++) {
                if (i - coins[j] >= 0 && dp[i - coins[j]] != -1)
                    mid = min(mid, dp[i - coins[j]]);
            }
            if (mid == INT_MAX)
                dp[i] = -1;
            else
                dp[i] = mid + 1;
        }
        return dp[amount];
    }
};