1、思路

• dp[i]表示凑够总额i所需要的最少硬币数，初始化dp[0] = 0表示凑出总额0至少需要0枚硬币；

• 时间复杂度为 $O(NT)$，空间复杂度为 $O(T)$，其中$N$表示硬币种类数，$T$表示目标总额。

2、代码

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

        for (int i = 1; i <= amount; ++ i)
        {
            dp[i] = amount + 1;             //用一个界外值标记不存在的情况
            for (int &coin : coins)         //遍历每一个硬币
            {
                if (i >= coin)
                {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp.back() > amount ? -1 : dp.back();
    }
};