题目描述
给你一个整数数组 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.length <= 121<=coins.length<=12
1<=coins[i]<=231−11 <= coins[i] <= 2^{31} - 11<=coins[i]<=231−1
0<=amount<=1040 <= amount <= 10^40<=amount<=104
思路
动态规划模板，dp[i]表示第i种硬币所需要的最少数量，可以由coins数量硬币中转移过来，也就是dp[i]=dp[i - coins[j]] + 1。
代码
classSolution{public:intcoinChange(vector<int>&coins,intamount){vector<int>dp(amount+1,0);intn=coins.size();for(inti=1;i<=amount;++i){dp[i]=INT_MAX;for(intj=0;j<n;++j){if(i>=coins[j]&&dp[i-coins[j]]!=INT_MAX){dp[i]=min(dp[i],1+dp[i-coins[j]]);}}}if(dp[amount]==INT_MAX)return-1;elsereturndp[amount];}};
