Leetcode_322_Coin Change

[lihe]

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:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

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

分析：贪心算法在个别面值的组合的时候是可以的，比如我们使用的人民币，但此题的面值不确定，故不能使用贪心算法；可以使用动态规划法。

算法思路：

1. dp[i]代表金额i的最优解，dp[0]、dp[1]...dp[n-1]都是已知的；
2. 金额i可由金额i-1和面值1组合、也可由金额i-2和面值2组合；
3. dp[i] = min(dp[i-1], dp[i-2]...) + 1

class Solution{
public:
    int coinChange(std::vector<int> &coins, int amount){
        std::vector<int> dp;
        for(int i = 0; i <= amount; i++){
            dp.push_back(-1);
        }
        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 - coins[j]] != -1){
                    if(dp[i] == -1 || dp[i] > dp[i - coins[j]] + 1){
                        dp[i] = dp[i - coins[j]] + 1;
                    }
                }
            }
        }
        return dp[amount];
    }
};