目录
前置知识：零钱兑换II的解析
在做完全背包问题算组合个数的时候，发现两层循环的先后不一样会导致输出结果的不同。其中：
1. 当外层循环为物品元素时，结果为组合结果，即结果序列与顺序无关，例如：[1,0] 和 [0,1] 算同一种结果；
2. 当外层循环为背包容量时，结果为排列结果，即结果序列与顺序相关，例如：[1,0] 和 [0,1] 算不同结果。
在力扣377. 组合总和中，求的是排列结果的种数，将物品放在了内层循环中遍历。由于不是特别理解两层循环先后顺序对输出结果的影响，因此在此进行深入理解与分析两种遍历方式的具体过程。
为了阐述方便，我们使用力扣377. 组合总和的题干对循环顺序进行模拟与分析：
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
1. 外层循环：物品，内层循环：背包容量
由于动态规划的题目模版中往往将物品作为行，背包容量作为列，因此大家通常会习惯将物品放在外层遍历。
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j <= target; j++) {
if (j >= nums[i]) {
dp[j] += dp[j - nums[i]];
}
}
}但是如果使用该顺序遍历力扣377. 组合总和中的题目会发现输出错误的结果4，原因是输出了组合的结果：
输出：
(1, 1, 1, 1)
(1, 1, 2)
(1, 3)
(2, 2)
对比预期输出我们会发现，(1, 1, 2)、(1, 2, 1)、(2, 1, 1)被当成了同种元素。
以第一层dp[4]为例子，我们将二维dp数组的所有结果列出来进行观察（其中加粗字段表示相比上一个状态新增的元素序列）：
接下来以第二层dp[4]为例子：
我们可以发现，先遍历背包容量的话，新增部分的元素（红色部分）会从当前行进行寻找，并且在遍历到下一行之前，不会有当前行下方的物品出现。我们可以发现，新增的序列最后一个数都是本行新增的物品数。
2. 外层循环：背包容量，内层循环：物品
该题目正确答案应该使用外层循环遍历背包容量
for (int j = 0; j <= target; j++) {
for (int i = 0; i < nums.length; i++) {
if (j >= nums[i]) {
dp[j] += dp[j - nums[i]];
}
}
}同样地，以第一层dp[4]为例子，我们将二维dp数组的所有结果列出来进行观察（其中加粗字段表示相比上一个状态新增的元素序列）：
我们可以观察到，和求组合数的遍历不同，第一层的当前状态中，新增部分的元素（红色部分）会从上一列的最后一行寻找。
接下来以第二层dp[4]为例子：
我们可以观察到当前状态，已经存在了(2,1,1)与(1,2,1)的情况下，仍然加入了(1,1,2)。因为在每个背包容量（dp的列）的情况下，我们都把所有物品元素遍历了一遍。
3. 总结规律
1. 求组合序列的总数：物品放外层循环遍历，按照dp数组习惯遍历
2. 求排列序列的总数：物品放内层循环遍历（想想dp经典题目跳楼梯，本质上是nums={1,2}的完全背包求排列数问题），每一个背包容量（列）的情况都会遍历所有物品（行）