Description
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.
Explain
這道題，一看排截，以為用貪心法做冤狡。但是經(jīng)過(guò)大神提點(diǎn)偎血，這題用DP做更簡(jiǎn)單。然后上網(wǎng)搜一下DP的講解蒂胞，這題是用來(lái)理解DP的最好例子昼捍。舉個(gè)例子：用dp[i] 代表 i元需要的最少塊硬幣，硬幣有1,2,5
i=0時(shí)檐束，dp[i] = 0；
i = 1 時(shí)束倍，dp[i] = min(dp[1-1] + 1, dp[i]) = 1
i = 2 時(shí)被丧，dp[i] = min(dp[2-1] + 1, dp[i]) = 2
。绪妹。甥桂。。
以上的例子的意思是邮旷，當(dāng)需要i元時(shí)黄选，只要再加一塊1或2或5的硬幣就可以得到答案，而i-1或i-2或i-5的答案已經(jīng)是得到的了婶肩。那么dp方程就是
dp[i] = min(dp[i], dp[i - coins[j]] + 1)
那最多就需要兩重循環(huán)就得出答案了
Code
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if (coins.empty() || amount == 0) return 0;
sort(coins.begin(), coins.end());
vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.size(); j++) {
if (i - coins[j] < 0) continue;
if (dp[i - coins[j]] == -1) continue;
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
if (dp[i] == INT_MAX) dp[i] = -1;
}
return dp.back();
}
};
