建站专业定制,p9制作公司,免费 开源 企业网站,大型网站开发用什么技术关于如何确定遍历顺序
322. 零钱兑换中#xff0c;本题求钱币最小个数#xff0c;那么钱币有顺序和没有顺序都可以#xff0c;都不影响钱币的最小个数。
所以本题并不强调集合是组合还是排列。
如果求组合数就是外层for循环遍历物品#xff0c;内层for遍历背包。
如果求…关于如何确定遍历顺序
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] 1coins[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的良苦用心那。
相信大家看完之后对背包问题中的遍历顺序有更深的理解了。
