Leetcode-Coin Change

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

这道题，一看，以为用贪心法做。但是经过大神提点，这题用DP做更简单。然后上网搜一下DP的讲解，这题是用来理解DP的最好例子。举个例子：用dp[i] 代表 i元需要的最少块硬币，硬币有1,2,5
i=0时，dp[i] = 0；
i = 1 时，dp[i] = min(dp[1-1] + 1, dp[i]) = 1
i = 2 时，dp[i] = min(dp[2-1] + 1, dp[i]) = 2
。。。。
以上的例子的意思是，当需要i元时，只要再加一块1或2或5的硬币就可以得到答案，而i-1或i-2或i-5的答案已经是得到的了。那么dp方程就是

dp[i] = min(dp[i], dp[i - coins[j]] + 1)

那最多就需要两重循环就得出答案了

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();
    }
};