思路：从1块钱遍历到总金额，用dp计算凑成每种金额最少所需的硬币数。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int max_cnt = amount + 1;
        vector<int> f(amount + 1, max_cnt);

        f[0] = 0;
        for (int i = 1; i <= amount; ++ i)              //从一块钱遍历到amount块钱
            for (int j = 0; j < coins.size(); ++ j)     //i块钱能由哪些硬币组成
                if (coins[j] <= i)                      //当前硬币面值小于i块钱，考虑将它加入
                    f[i] = min(f[i], f[i - coins[j]] + 1);

        return f[amount] > amount ? -1 : f[amount];     //结果若还是初始时的amount + 1则无解
    }
};