322. Coin Change 322. 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. 322. Coin Change

---

给定一堆硬币数组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。

二刷。常规DP思路，类似于背包问题，假设dp[i][j]表示用前i类硬币，组成j元钱的最少硬币数目。有两种情况，一是这次不用第i类硬币，dp[i][j]=dp[i-1][j]；二是这次用第i类硬币，则还需要凑齐j-coins[i]块钱，因为每类硬币数量无限，所以用了i之后还可以用i，即dp[i][j]=dp[i][j-coins[i]]。两种情况取最小值即可。完整代码如下：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<vector<long long>> dp(n + 1, vector<long long>(amount + 1, 0));
        for(int j = 1; j <= amount; ++j) dp[0][j] = INT_MAX;
        
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= amount; ++j) {
                dp[i][j] = dp[i - 1][j];
                if(j >= coins[i - 1]) dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
            }
        }
        if(dp[n][amount] >= INT_MAX) return -1;
        else return dp[n][amount];
    }
};

本代码提交AC，用时344MS。