leetcode 322 Coin Change-蒲公英云

leetcode 322 Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

[122,112,383,404,25,368]6977

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int>eachnum = coins;
        //从大到小排序
        sort(eachnum.begin(), eachnum.end());
        for (int i = 0; i < coins.size(); i++)
            coins[coins.size() - 1 - i] = eachnum[i];
        for (int i = 0; i < coins.size(); i++)
            eachnum[i] = 0;
        if (amount == 0)
            return 0;
        //总额小于硬币最小面额，不能被表示
        if (amount < coins[coins.size() - 1])
            return -1;
        if (coins.size() == 1 && amount%coins[0] != 0)
            return -1;
        //若不能用所给的硬币表示时的终止条件
        vector<int>ending;
        ending = eachnum;
        ending[coins.size() - 1] = amount / coins[coins.size() - 1];
        int min = 1000000;
        int it = 0;
        int remain = amount;
        bool flag = false;
        while (eachnum != ending)
        {
            eachnum[it] += remain / coins[it];
            remain -= coins[it] * (remain / coins[it]);
            if (remain == 0)
            {
                flag = true;
                int toret = 0;
                for (int i = 0; i<coins.size(); i++)
                    toret += eachnum[i];
                if (toret<min)
                    min = toret;
                for (int kkk = coins.size() - 2; kkk >= 0; kkk--)
                {
                    if (eachnum[kkk]>0)
                    {
                        eachnum[kkk]--;
                        remain += coins[kkk] + coins.back()*eachnum.back();
                        eachnum.back() = 0;
                        it = 1 + kkk;
                        break;
                    }
                }
            }
            else if (remain < coins.back())
            {
                //达到终止条件
                for (int i = 0; i < coins.size(); i++)
                    if (eachnum[i]>0)
                    {
                        if (amount / coins[i] + (amount % coins[i]==0?0:1) >= min)
                            return min;
                        break;
                    }
                if (eachnum == ending)
                {
                    if (flag)
                        return min;
                    else
                        return -1;
                }
                for (int kkk = coins.size() - 2; kkk >= 0; kkk--)
                {
                    if (eachnum[kkk]>0)
                    {
                        eachnum[kkk]--;
                        remain += coins[kkk] + coins.back()*eachnum.back();
                        eachnum.back() = 0;
                        it = 1 + kkk;
                        break;
                    }
                }
            }
            else
            {
                it++;
            }
        }
    }
};

Time Limit Exceeded

Last executed input:
[58,92,387,421,194,208,231]
7798

转换思路，用动态规划方法求解

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount == 0)
            return 0;
        //从小到大排序
        sort(coins.begin(), coins.end());
        //总额小于硬币最小面额，不能被表示
        if (coins.empty() || amount < coins[0] || coins.size() == 1 && amount%coins[0] != 0)
            return -1;
        if (find(coins.begin(), coins.end(), amount) != coins.end())
            return 1;
        int minch = amount / coins[0] + 1;
        int k = 1;
        vector<int>dp(amount+1);
        for (int i = 1; i < dp.size(); i++)
        {
            int m = 1000000;
            for (int j = 0; j < coins.size(); j++)
                if (i >= coins[j] && dp[i - coins[j]] != -1)
                    m = min(dp[i - coins[j]] + 1, m);
                dp[i] = m == 1000000 ? -1 : m;
            }
        return dp[amount];
    }
};