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

解析：零钱兑换问题，给了一堆硬币和一个数值，要求计算出当前数组兑换成零钱的最小数量，如果无法兑换则返回-1。

思路：对于求极值问题，考虑动态规划思路。假设dp[i]表示数值i兑换成零钱后的最小数量，因为dp[0]=0，最终返回的结果为dp[amount]，因为申请的dp数组长度为amount+1。采用两层循环，外层i从1到amount，内存循环遍历零钱数组，如果当前零钱num小于i，表示i可以使用零钱num来兑换，因为此时dp[i]=dp[i-num]+1,因为需要选取最小值，所以dp[i]=min(dp[i],dp[i-num]+1)。通过递推关系也可以看出dp数组初始化时不能设置为INT_MAX，否则会超出，因此这里设置为amount+1。 具体代码如下：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int>dp(amount+1, amount+1);
        dp[0] = 0;
        for(int i=1; i <= amount; i++)
        {
            for(auto num : coins)
            {
                if(num <= i)
                {
                    dp[i] = min(dp[i], dp[i-num]+1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

参考：https://leetcode.com/problems/coin-change/discuss/77360/C%2B%2B-O(n*amount)-time-O(amount)-space-DP-solution