本题是运用完全背包的思想来求一个最小值问题。区别于 01 背包，完全背包问题就是每个物品可以不限个数地放入背包，相应的递推公式也会发生变化。
我们先考虑二维 dp 数组的情况，设状态 dp[i][j] 为考虑前 0-i 个钱币，凑足总额为 j 所需钱币的最少个数，可得出如下递推公式：
dp[i][j] = min(dp[i-1][j], dp[i-1][j-coins[i]]+1, dp[i-1][j-2*coins[i]]+2, ..., dp[i-1][j-k*coins[i]]+k, ...) // ①
即要么不使用面值为 i的硬币，要么使用 1个、2个、3个…… k个……面值为 i的硬币
我们将上式的 j 替换为 j-coins[i]，得：
dp[i][j-coins[i]] = min(dp[i-1][j-coins[i]], dp[i-1][j-2*coins[i]]+1, dp[i-1][j-3*coins[i]]+2, ..., dp[i-1][j-(k+1)*coins[i]]+k, ...) // ②
我们不难发现，① 式 min 中 dp[i-1][j] 后面的部分正好是 ② 式 + 1，将 ② 式代入 ① 式，得：
dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i]]+1) // ③
同 01 背包问题一样，我们对 dp 数组运用滚动数组的方法压缩到一维，最终的递推公式如下：
dp[j] = min(dp[j], dp[j-coins[i]]+1) // ④
虽然 ④ 式和 01 背包问题优化后的式子并无二致，但为了体现出优化前 ③ 式的状态转移关系，我们在遍历一维 dp 数组时需要从前往后（而不是 01 背包从后往前）遍历，这样就保证了 dp[j-coins[i]] 永远是先于 dp[j] 计算的。
代码实现如下：
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
vector<int> dp(amount + 1, amount + 1); // dp数组初始化为amount+1，作为最大值，方便下面取min的状态转移
dp[0] = 0; // 显然dp[0]初始化为0
for(int i = 0; i < n; i ++) {
for(int j = coins[i]; j <= amount; j ++) { // 注意完全背包的内层循环是从前往后遍历的
dp[j] = min(dp[j], dp[j - coins[i]] + 1);
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount]; // 若dp[amount]为amount+1，说明条件给出的硬币面额无法凑出amount
}
};