给你一个整数数组 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 <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
解题思路
状态表示
根据题目中说的每种硬币的数量是无限的，其实这就变成了 完全背包 问题了！硬币相当于是物品，硬币的金额相当于是体积，背包的体积就是总金额！
所以根据 “经验 + 题目要求”，可以得到 dp[i][j] 表示在前 i 个硬币中选，总金额正好等于 j，此时所需的最少的硬币个数！
状态转移方程
既然是完全背包问题，那么其实根据模板题稍微修改一下状态转移方程就能行了，而这道题其实就是从模板题的求最大价值，变成了求最少的硬币个数，仅此而已！
初始化
初始化还是一样，第一列我们不需要管，把它放到填表的时候一起填，具体原因之前有说过，其实就是因为第一列我们其实是不怕会越界的，因为我们有判断一个 j - v[i] >= 0 的情况，所以**不需要初始化第一列，跟着填表时候一起填就行**，后面也是如此！
而第一列这道题就要修改一下细节：
第一行表示有 0 个硬币，而第一个元素是因为背包空间也是为 0，所以是能满足的，只不过结果 0 个硬币！
而第一行其它元素则不同了，背包空间不为 0，那么此时就不满足背包空间装满，为了不影响后面填表求最小值，我们要将其初始化为足够大，但是最好不要用无穷大，因为可能会加一后溢出，所以我们用 0x3f3f3f3f 来代替！
遍历顺序
从上往下，从左往右遍历。
返回值
根据状态表示，返回最后一个位置 dp[n][amount]。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
// 创建dp表，dp[i][j]表示在前i个中选，总金额正好等于j，此时所需的最少硬币个数
int n = coins.size();
vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
// 初始化 -- 只需要初始化第一行
for(int j = 1; j <= amount; ++j)
dp[0][j] = 0x3f3f3f3f;
// 从上往下，从左往右填表
for(int i = 1; i <= n; ++i)
{
for(int j = 0; j <= amount; ++j)
{
dp[i][j] = dp[i - 1][j];
// 注意与原数组的下标映射关系
if(j >= coins[i - 1])
dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
}
}
return (dp[n][amount] == 0x3f3f3f3f ? -1 : dp[n][amount]);
}
};优化
所有的「背包问题」，都可以进行空间上的优化。
对于 完全背包 类型的，我们的优化策略是：
- 删掉第一维
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
// 创建dp表
int n = coins.size();
vector<int> dp(amount + 1, 0);
// 初始化
for(int j = 1; j <= amount; ++j)
dp[j] = 0x3f3f3f3f;
// 从上往下，从左往右填表
for(int i = 1; i <= n; ++i)
for(int j = coins[i - 1]; j <= amount; ++j)
dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);
return (dp[amount] == 0x3f3f3f3f ? -1 : dp[amount]);
}
};