LeetCode Coin Change

LeetCode 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.

Note:
You may assume that you have an infinite number of each kind of coin.


给定一堆硬币数组coins和一个总数amount,问最少用多少个硬币能凑齐这amount的钱数。每种面值的硬币数量无限。

一开始想到用贪心,即为了使硬币数最少,我们总是用小于等于amount的最大面值的硬币去凑。但是这样得到的结果不是最优的,而且有时候还可能得不到结果。比如coins=[2,5,7,8], amount=19,如果用贪心的思路,首先取8,amount=19-8=11;再取8,amount=11-8=3;再取2,amount=3-2=1;没有硬币可取了,这样就凑不齐19。但是如果不取8,而是取19=7+7+5,则可以用3枚硬币凑齐。

一般不能用贪心得到全局最优解的时候,用DP总是能得到全局最优解的。

假设dp[i]表示凑齐钱数为i最少需要的硬币数,则dp[i]=min(dp[i-coins[j]]+1, dp[i])。这个递推式的意思是说,如果要凑齐钱数i,我们看看能不能用第j个硬币,如果能的话,用之前需要凑齐i-coins[j]的钱数,所以总的硬币数就是凑齐i-coins[j]的硬币数加上1,这个1就是j这个硬币。我们需要遍历所有j求最小。最后dp[amount]就是全局最优解。

完整代码如下:

class Solution {
public:
	int coinChange(vector<int>& coins, int amount) {
		int mmax = amount + 1, ans = mmax;
		vector<int> dp(amount + 1, mmax);
		dp[0] = 0;
		for (int i = 1; i <= amount; ++i) {
			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] >= mmax ? -1 : dp[amount];
	}
};

本代码提交AC,用时33MS。

Leave a Reply

Your email address will not be published. Required fields are marked *