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)。
