Give you an array of integers coins , Coins of different denominations ; And an integer amount , Represents the total amount . Calculate and return the amount needed to make up the total amount The minimum number of coins . If no combination of coins can make up the total amount , return  -1 . You can think of the number of coins of each kind as infinite .

1. reflection

    The conventional solution to this problem is to use dynamic programming . The topic of dynamic planning , The key is the transfer equation . The idea of this question is relatively simple , Some integer n It can be regarded as the least way to exchange coins n-1 The minimum coin exchange method + One with a face value of 1 The coin of . Therefore, the following transfer equations can be listed

Usually if you can use the topic of dynamic programming , It can also be solved recursively , The idea is exactly the same as that of dynamic planning , Find the optimal subproblem . Because there are a lot of repeated solutions in recursion , You can use memos to optimize , Its effect is equivalent to dynamic programming , But because recursion requires repeated calls to functions , Its efficiency is lower than that of dynamic programming .

        Another possible way of thinking is to use backtracking , For integers n, from coins Select a face value coin The coin of , To add to track In the list , At this time, it becomes an integer n-coin, Repeat the above steps , Until the integer becomes 0, here track The size of is the total number of coins required for this method .

 2. Coding

(1) Based on Dynamic Planning

 int coinChange(vector<int>& coins, int amount)
 {
        if (amount < 0)
            return -1;

        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i)
        {
            for (int coin : coins)  // Transfer according to the transfer equation 
            {
                if (i - coin < 0) continue;    //n<0 dp[n]=-1  Don't deal with 
                if (dp[i - coin] == -1) continue; //dp[n]=-1  Don't deal with 
                int submc = dp[i - coin] + 1; //n>0 
                dp[i] = min(dp[i], submc);
            }

            dp[i] = dp[i] < INT_MAX ? dp[i] : -1;
        }

        return dp[amount];
 }

（2） Based on recursion

int coinChange(vector<int>& coins, int amount)
{
        if (amount == 0)
            return 0;

        if (amount < 0)
            return -1;

        int minc = INT_MAX;
        for (int coin : coins)
        {
            int sub_minc = coinChange(coins, amount - coin);
            if (sub_minc == -1) continue;
            minc = min(minc, sub_minc + 1);
        }

        return minc < INT_MAX ? minc : -1;

}

（3） Memo based recursion

    unordered_map<int, int> memocoin;
    int coinChange(vector<int>& coins, int amount)
    {
        if (amount == 0)
            return 0;

        if (amount < 0)
            return -1;

        if (memocoin.count(amount) != 0)
            return memocoin[amount];

        int minc = INT_MAX;
        for (int coin : coins)
        {
            int sub_minc = coinChange(coins, amount - coin);
            if (sub_minc == -1) continue;
            minc = min(minc, sub_minc + 1);
            memocoin[amount] = minc;
        }

        return minc < INT_MAX ? minc : -1;

    }

（4） to flash back

    int minn = LONG_MAX;
    int coinChange(vector<int>& coins, int amount)
    {
        vector<int> track;
        helpperCoinChange(coins, track, amount);
        return minn < LONG_MAX ? minn : -1;

    }
    void helpperCoinChange(vector<int> sl, vector<int> track, int amount)
    {
        if (amount == 0)
        {
            minn = minn < track.size() ? minn : track.size();
            return;
        }

        for (int i : sl)
        {
            if (i > amount)
                continue;

            track.push_back(i);
            helpperCoinChange(sl, track, amount-i);
            track.pop_back();
        }

    }