题目描述：给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

方法1：递归，超时，INT_MAX表示最大的整数，不是MAX_INT

class Solution {
public:
    int count = INT_MAX;

    void find(vector<int>& coins, int amount,int num){
        if(amount == 0) count = min(count,num);//更新count
        if(amount < 0) return;

        for(int coin : coins){
            find(coins,amount-coin,num+1);
        }
    }

    int coinChange(vector<int>& coins, int amount) {
        find(coins,amount,0);
        return count==INT_MAX?-1:count;
    }
};

方法2：动态规划，类似于跳楼梯，（以[1, 2, 5], 11为例），问题就转换成：青蛙每次能跳 1 或 2 或 5 阶，跳到11阶有多少种跳法，11 阶的数量也就取决于跳到 min（ 第6阶、第9阶、第10阶 ） + 1

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,amount+1);
        dp[0] = 0;
        for(int i=1;i<=amount;i++){ //从1开始更新dp数组
            for(int j=0;j<coins.size();j++){
                if((i - coins[j]) >= 0) dp[i] = min(dp[i],dp[i - coins[j]]+1);
            }
        }
        return dp[amount] == amount+1? -1:dp[amount];
    }
};

优化：对coins按从小到大的顺序排序，i-coin小于0，跳出

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,amount+1);
        dp[0] = 0;
        sort(coins.begin(),coins.end());
        for(int i=1;i<=amount;i++){ //从1开始更新dp数组
            for(int j=0;j<coins.size();j++){
                if((i - coins[j]) < 0) break;
                dp[i] = min(dp[i],dp[i - coins[j]]+1);
            }
        }
        return dp[amount] == amount+1? -1:dp[amount];
    }
};