动态规划
给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回-1 。
你可以认为每种硬币的数量是无限的。
跟完全平方数解法完全一致，不过完全平方转移状态用的的是满足条件的所有平方数
而零钱兑换转移状态的是能使用的硬币面值
dp[i]为整数总面额为i时的最少硬币个数
状态转移方程dp[i]=min(dp[i-coin])+1
边界条件dp[0]=0
class Solution {public: int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount+1); for(int i=1;i<=amount;i++){ int min_=INT_MAX; for(auto &x:coins){ if(i-x>=0&&dp[i-x]!=-1) min_=min(min_,dp[i-x]); } if(min_==INT_MAX) dp[i]=-1; else dp[i]=min_+1; } return dp[amount]; }};
