1. question: 零钱对换II(中等)
给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/coin-change-2
示例 1:
1 2 3 4 5 6 7
| 输入:amount = 5, coins = [1, 2, 5] 输出:4 解释:有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
|
示例 2:
1 2 3
| 输入:amount = 3, coins = [2] 输出:0 解释:只用面额 2 的硬币不能凑成总金额 3 。
|
示例 3:
1 2
| 输入:amount = 10, coins = [10] 输出:1
|
提示:
1 2 3 4
| 1 <= coins.length <= 300 1 <= coins[i] <= 5000 coins 中的所有值 互不相同 0 <= amount <= 5000
|
2. answers
在了解了完全背包之后,这道题还是比较简单的。首先可以明确递推公式:对于当前硬币,在当前容量下,其所有组合种类由两种组成:
- 如果选他,那么一定是在留有足够容量的背包时,并且是在本硬币的情况下选择(而不再是01背包中的i-1);
- 不选他,那么就是在上一任硬币,在此容量下的最优解。
- 二者之和就是本硬币,在本容量下的最优解。
注意,初始化时,因为存在硬币和amount相等的情况,即此时,如果选他,那么就需要留有足够空间时的状态,显然会回退到dp[0],这时,其实是一种方式,因此,dp[0]初始化为1。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| public class Solution_0124 {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
for (int i = 0; i < dp.length; i++) { if(i % coins[0] == 0) dp[i] = 1; }
for (int i = 1; i < coins.length; i++) { for (int j = 0; j < dp.length; j++) {
if(j < coins[i]) dp[j] = dp[j];
else dp[j] = dp[j] + dp[j-coins[i]]; } }
return dp[amount]; }
public static void main(String[] args) { System.out.println();
Solution_0124 s = new Solution_0124();
int amount = 3; int[] coins = {2};
System.out.println(s.change(amount, coins)); } }
|
2.1 注意
上面是最常规的写法,即外层遍历物品,内层遍历容量,这是正常结果。
那么外层遍历容量,内层遍历物品呢?这种写法对不对呢?答案是不对的(在一维动态数组下)。
因为对于完全背包问题,元素是允许重复的,显然外层遍历物品,内层遍历容量,这种方式下,选取的物品相对位置是固定的,即无论怎么选择,只要选取物品1和物品2,那么1一定是在2前面,因为先遍历的它。
而外层遍历容量,内层遍历物品。此时,每遍历完一遍物品,那么下一个容量下,就会受到上一个容量下最后一个物品时的结果影响。(因为dp[j] = dp[j] + dp[j-coins[i]],以及dp[j] = dp[j]),而在当前容量下,后续的物品回退到前面容量时,得到的结果,就会和上一个物品之间有重复(即dp[j]和dp[j-coins[i]]有重复)。
比如还是本题,物品有[1,2,5],背包容量为5,在一维数组外层遍历容量,内层遍历物品时,在dp[1]的时候,只有一个结果(1);在dp[2]的时候有两个结果(1,1)和(2)【注意,一维数组下,此时dp[2]=2】;那么在dp[3]的时候,在物品[1]时会用到dp[2],即有两个结果(1,1,1)和(2,1),那么在物品[2]时,可以选本物品【dp[i-coins[j]]】,会回退到dp[1],即结果为(1,2),同时也可以不取本物品【dp[i]】,直接用上面的结果,即(1,1,1)和(2,1),此时二者出现了重复,即本方法将(1,2)和(2,1)看成了不同的组合,也就是排列。
所以说:
- 如果是组合,要先遍历物品(外层),再遍历背包(内层)。
- 如果是排列,要先遍历背包(外层),再遍历物品(内层)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| * TODO 结果表明,确实不一样,发现了不同的结果。这是问什么呢? * 首先,如果外层遍历背包尺寸,内层遍历物品,显然在dp[i-1]遍历完之后,再遍历dp[i]的时候,内层遍历物品, * 比如遍历第1个物品,此时会用到dp[i-1]或者dp[i-x],但是此时的dp[i-x]的结果,很有可能是上一轮第3个物品更新过的。 * 那么,即在本轮第一个物品的时候,就用到了上面第3个物品,假设本结果的物品顺序是 [3,1] * 那么当在本轮第3个物品的时候,【此时,物品1一定是满足要求的】,除了上面的[3,1],肯定会回退到[i-x]时的情况,即刚选了物品1 * 那么本次结果就是[1,3] * 显然外层遍历背包容量,会导致结果重复(即实际结果是排列,而不是组合) * * TODO 更加直观地说,外层遍历背包容量,内层遍历物品。 * 可以将背包容量看成是一个数组,每遍历一遍,就相当于在数组中摆放了一个物品【即确定了整个数组中每个位置上的物品】。 * 【而本题,虽然没有明确具体的物品,但是是将本位置上的所有选择进行了计数,也相当于放置了物品】 * 假设物品有[1,2,5],背包容量为5. * 显然,在容量[1]的时候,可以放物品1,在[2]的时候,可以放两个1,一个2, * 那么在[3]的时候,先遍历物品1,即此时会回退到[2],显然会用到[2]的结果,即此时的结果就是(1,1,1),(2,1) * 那么在遍历物品2的时候呢,此时就会回退到[1],会用到该结果,那么此时的结果就是(1,2) * 那么在遍历物品3的时候,会用到[0]的结果,那么此时的结果就是(3) * 因为:dp[i] = dp[i] + dp[i-coins[j]],即左侧dp[i]为当前物品,而右侧dp[i]是上一个物品,dp[i-coins[j]]为回退到的元素 * 显然,等号右侧的两个因子,包含了重复结果。 * * 显然,外层遍历背包容量,内层遍历物品,因为允许重复使用,那么就会形成排列。 * * TODO 那么为什么外层遍历物品,内层遍历背包容量,不是这种结果呢? * 因为物品始终是自上而下遍历的,即不存在重复遍历物品的情况,总体上说,物品之间的相对位置是一定的。所以也就不会出现排列问题。
|
3. 备注
参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com),代码随想录 (programmercarl.com)。