昆明公司做网站如何做推广推广技巧
关于如何确定遍历顺序
322. 零钱兑换中，本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。
所以本题并不强调集合是组合还是排列。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
在动态规划专题我们讲过了求组合数是动态规划：518.零钱兑换II (opens new window)，求排列数是动态规划：377. 组合总和 Ⅳ (opens new window)。
所以本题的两个for循环的关系是：外层for循环遍历物品，内层for遍历背包或者外层for遍历背包，内层for循环遍历物品都是可以的！
那么我采用coins放在外循环，target在内循环的方式。
本题钱币数量可以无限使用，那么是完全背包。所以遍历的内循环是正序
综上所述，遍历顺序为：coins（物品）放在外循环，target（背包）在内循环。且内循环正序。
求组合数
例题：518.零钱兑换II
这是一道典型的背包问题，一看到钱币数量不限，就知道这是一个完全背包。
但本题和纯完全背包不一样，纯完全背包是凑成背包最大价值是多少，而本题是要求凑成总金额的物品组合个数！
注意题目描述中是凑成总金额的硬币组合数，为什么强调是组合数呢？
例如示例一：
5 = 2 + 2 + 1
5 = 2 + 1 + 2
这是一种组合，都是 2 2 1。
如果问的是排列数，那么上面就是两种排列了。
组合不强调元素之间的顺序，排列强调元素之间的顺序。 其实这一点我们在讲解回溯算法专题的时候就讲过了哈。
那我为什么要介绍这些呢，因为这和下文讲解遍历顺序息息相关!
- 确定遍历顺序
本题中我们是外层for循环遍历物品（钱币），内层for遍历背包（金钱总额），还是外层for遍历背包（金钱总额），内层for循环遍历物品（钱币）呢？
我在动态规划：关于完全背包，你该了解这些！ (opens new window)中讲解了完全背包的两个for循环的先后顺序都是可以的。
但本题就不行了！
因为纯完全背包求得装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行！
而本题要求凑成总和的组合数，元素之间明确要求没有顺序。
所以纯完全背包是能凑成总和就行，不用管怎么凑的。
本题是求凑出来的方案个数，且每个方案个数是为组合数。
那么本题，两个for循环的先后顺序可就有说法了。
我们先来看 外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况。
代码如下：
for (int i = 0; i < coins.size(); i++) { // 遍历物品for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量dp[j] += dp[j - coins[i]];}
}假设：coins[0] = 1，coins[1] = 5。
那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。
所以这种遍历顺序中dp[j]里计算的是组合数！
如果把两个for交换顺序，代码如下：
for (int j = 0; j <= amount; j++) { // 遍历背包容量for (int i = 0; i < coins.size(); i++) { // 遍历物品if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];}
}背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。
此时dp[j]里算出来的就是排列数！
可能这里很多同学还不是很理解，建议动手把这两种方案的dp数组数值变化打印出来，对比看一看！（实践出真知）
2.举例推导dp数组
输入: amount = 5, coins = [1, 2, 5] ，dp状态图如下：
求排列数
例题：377. 组合总和 Ⅳ
本题题目描述说是求组合，但又说是可以元素相同顺序不同的组合算两个组合，其实就是求排列！
弄清什么是组合，什么是排列很重要。
组合不强调顺序，(1,5)和(5,1)是同一个组合。
排列强调顺序，(1,5)和(5,1)是两个不同的排列。
但其本质是本题求的是排列总和，而且仅仅是求排列总和的个数，并不是把所有的排列都列出来。
如果本题要把排列都列出来的话，只能使用回溯算法爆搜。
- 确定遍历顺序
个数可以不限使用，说明这是一个完全背包。
得到的集合是排列，说明需要考虑元素之间的顺序。
本题要求的是排列，那么这个for循环嵌套的顺序可以有说法了。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
如果把遍历nums（物品）放在外循环，遍历target的作为内循环的话，举一个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合，因为nums遍历放在外层，3只能出现在1后面！
所以本题遍历顺序最终遍历顺序：target（背包）放在外循环，将nums（物品）放在内循环，内循环从前到后遍历。
2.举例来推导dp数组
class Solution {public int combinationSum4(int[] nums, int target) {// 初始化dp数组，dp[i]表示目标和为i的所有组合数int[] dp = new int[target + 1];// 目标和为0时只有一种情况，即不选择任何元素dp[0] = 1;// 遍历每个从0到target的值for (int i = 0; i <= target; i++) { //遍历背包// 对于每个值i，遍历数组中的每个数for (int j = 0; j < nums.length; j++) { //遍历物品// 如果当前值i大于等于数组中的数nums[j]if (i >= nums[j]) { //背包容量大于物品重量// 将dp[i - nums[j]]的值加到dp[i]中// 这意味着通过添加nums[j]到组合中，我们找到了新的组合数//dp[i] += dp[i - nums[j]];dp[i] = dp[i] + dp[i - nums[j]]; }}}// 返回dp[target]，即目标和为target的所有组合数return dp[target];}
}
- 时间复杂度: O(target * n)，其中 n 为 nums 的长度
- 空间复杂度: O(target)
C++测试用例有两个数相加超过int的数据，所以需要在if里加上dp[i] < INT_MAX - dp[i - num]。
但java就不用考虑这个限制，java里的int也是四个字节吧，也有可能leetcode后台对不同语言的测试数据不一样。
总结
细心的同学看网上的题解，可能看一篇是遍历背包的for循环放外面，看一篇又是遍历背包的for循环放里面，看多了都看晕了，到底两个for循环应该是什么先后关系。
能把遍历顺序讲明白的文章几乎找不到！
这也是大多数同学学习动态规划的苦恼所在，有的时候递推公式很简单，难在遍历顺序上！
但最终又可以稀里糊涂的把题目过了，也不知道为什么这样可以过，反正就是过了。
那么这篇文章就把遍历顺序分析的清清楚楚。
动态规划：518.零钱兑换II (opens new window)中求的是组合数，动态规划：377. 组合总和 Ⅳ (opens new window)中求的是排列数。
而本题是要求最少硬币数量，硬币是组合数还是排列数都无所谓！所以两个for循环先后顺序怎样都可以！
这也是我为什么要先讲518.零钱兑换II 然后再讲本题即：322.零钱兑换，这是Carl的良苦用心那。
相信大家看完之后，对背包问题中的遍历顺序有更深的理解了。