LeetCode322：零钱兑换

题目链接：322. 零钱兑换 - 力扣（LeetCode）

代码如下

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for(int i = 0; i < coins.size(); i++)
        {
            for(int j = coins[i]; j <= amount; j++)
            {
                if(dp[j - coins[i]] != INT_MAX)  //这个也就是之前的都被初始化完毕，才能往后进行
                {
                    dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
                }
            }
        }
        if(dp[amount] == INT_MAX)   return -1;  //这个就是硬币书凑不出amount了，所以dp[amount]只能为INT_MAX
        return dp[amount];
    }
};

这个题目其实也就是相当于我们写前面那个零钱组合一样，但是之前的那个零钱组合是相求出组合数有多少个，而这个是找出能够组合的钱币然后输出最小的组成数，很明显，这个题目所说的amount也就是我们所要的背包容量，我们接下来第一步先确定dp[j]的含义，dp[j]也就是我们的背包最小容量，dp递推公式是dp[j] = min(dp[j], dp[j - coins[i] + 1])这里为什么是+1而不是加coins[i], 因为题目给的是，要求出的硬币数量，而不是要求出能装的背包大小，for循环里面的有一个判断条件，也就是if(dp[j - coins[i]] != INT_MAX),这个是为什么呢，因为我们需要找到当前dp数组是被初始化的，然后我们才能进行下一步赋值，如果这个数组没有被初始化了，也就是不满足这个背包问题了。