题目描述

给定 $n$ 种不同硬币的面值，以及需要凑出的总面值 $total$。请写一个函数，求最少需要多少硬币，可以凑出 $total$ 的钱。
如果不存在任何一种拼凑方案，则返回-1。

注意：
你可以假定所有硬币都有无限多个。

样例1

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

样例2

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

算法

(动态规划) $O(nm)$

完全背包问题。
相当于有 $n$ 种物品，每种物品的体积是硬币面值，价值是1。问装满背包最少需要多少价值的物品？

状态表示： f[j] 表示凑出 $j$ 价值的钱，最少需要多少个硬币。
第一层循环枚举不同硬币，第二层循环从小到大枚举所有价值（由于每种硬币有无限多个，所以要从小到大枚举），然后用第 $i$ 种硬币更新 f[j]：f[j] = min(f[j], f[j - coins[i]] + 1)。

时间复杂度分析：令 $n$ 表示硬币种数，$m$ 表示总价钱，则总共两层循环，所以时间复杂度是 $O(nm)$。

C++ 代码

class Solution {
public:

    int INF = 1000000000;

    int coinChange(vector<int>& coins, int amount) {
        vector<int> f(amount + 1, INF);
        f[0] = 0;
        for (int i = 0; i < coins.size(); i ++ )
            for (int j = coins[i]; j <= amount; j ++ )
                f[j] = min(f[j], f[j - coins[i]] + 1);
        if (f[amount] == INF) f[amount] = -1;
        return f[amount];
    }
};