LeetCode_124_CoinChange2


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

在了解了完全背包之后,这道题还是比较简单的。首先可以明确递推公式:对于当前硬币,在当前容量下,其所有组合种类由两种组成:

  1. 如果选他,那么一定是在留有足够容量的背包时,并且是在本硬币的情况下选择(而不再是01背包中的i-1);
  2. 不选他,那么就是在上一任硬币,在此容量下的最优解。
  3. 二者之和就是本硬币,在本容量下的最优解。

注意,初始化时,因为存在硬币和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) {

// 定义数组,表示在当前容量J的情况下,当前及其前面元素所能形成总值为J的组合数。
int[] dp = new int[amount + 1];

// 初始化第一个面值下的状态,注意这里是组合数。
// 即能够整除,才说明,能够组成这种总面值
// TODO 这里,其实dp[0]应该为1,因为存在这样的情况,即面值金额为5,并且刚好等于amount,那么此时其实这种情况就是一种选择
// TODO 但是,如果dp[0]为0,显然 dp[5-5] = 0,这样就忽略了这种情况。
// TODO 本质上,第一个元素不选也是一种选择。
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 = 5;
// int[] coins = {1, 2, 5};

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. 如果是排列,要先遍历背包(外层),再遍历物品(内层)。
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)


文章作者: 浮云
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
  目录