动态十三： 零钱兑换

题目地址： https://leetcode-cn.com/problems/coin-change/
题目描述：
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1： 输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1
示例 2： 输入：coins = [2], amount = 3 输出：-1
示例 3： 输入：coins = [1], amount = 0 输出：0
示例 4： 输入：coins = [1], amount = 1 输出：1
示例 5： 输入：coins = [1], amount = 2 输出：2
提示：
1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

参考代码：

lass Solution {
public:
    int coinChange(vector<int>& coins, int amount) {

        //dp[j] = d[j] dp[j-coint[i]] +1
        
        vector<int> dp = vector<int>(amount+1,INT_MAX);
        
        dp[0] = 0;
        for (int i = 0; i<coins.size(); i++) {
            
            for (int j = coins[i]; j<=amount;j++) {
                
                if (j>=coins[i] && dp[j-coins[i]] != INT_MAX) {
                    
                    dp[j] = min(dp[j],dp[j-coins[i]]+1);
                }
            }
            
        }
        
        if (dp[amount] == INT_MAX) {
            return  -1;
        }
        return dp[amount];

    }
};

参考链接： https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0322.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2.md