leetcode 322 Coin Change

绝地灬酷狼 2022-08-20 10:30 2阅读 0赞

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];
    	}
    };