LeetCode/零钱兑换

动态规划

给你一个整数数组 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];    }};