LeetCode518：零钱兑换

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

代码如下

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<unsigned int> dp(amount + 10, 0);
        dp[0] = 1;
        for (int i = 0; i < coins.size(); i++) { // 遍历物品
            for (int j = coins[i]; j <= amount; j++) { // 遍历背包
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
};

首先来讲一下这个代码的一个需要注意的语法 vector<unsigned int> dp(amount + 10, 0);这个至少对于我来说我是第一次见的,这个作用就是unsigned int, 也就是无符号整型,也就是说范围是在1~2^31-1,  而平常的int其实是signed int的缩写, 所以来说, 这个范围是-2^31-1 ~ 2^31-1这个范围.

题目讲解：首先我们要知道这个题目要求的是有几种方法可以凑成这个amount，也就是我把amount当成一个背包容量，既然说钞票无限使用，我们肯定想到的是用完全背包。这个题目递推公式和之前的（leetcode494：目标和题目）一样的方法推到出来的，然后该初始化了，dp[0] = 1；这个是为了能够递推后面的值，要是初始化为0的话，那么后面的值是无法被覆盖的。

两个for循环颠倒的意义

第一个：先遍历物品再遍历背包(组合数)

for (int i = 0; i < coins.size(); i++) { // 遍历物品
    for (int j = coins[i]; j <= amount; j++) { // 遍历背包

这个求出来的是凑出这个amount的组合数，为什么这么说的，因为先遍历物品，肯定是先遍历1，然后遍历2，所以背包里面的组合就是有顺序的，{1，2}

第二个：先遍历背包再遍历物品（排列数）

for (int j = 0; j <= amount; j++) { // 遍历背包
    for (int i = 0; i < coins.size(); i++) { // 遍历物品

这个求出来的是凑出这个amount的排列数，因为是把背包定下来的，背包里面放入物品1，2，3.....，所以来说背包里面的物品是没有先后顺序的，所组成的数就是{1，2}，{2，1},这两个都能讲的通.