题目链接：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},这两个都能讲的通.