LeetCode_126_CoinChange


1. question: 零钱兑换(中等)

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。

你可以认为每种硬币的数量是无限的。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/coin-change

示例 1:

1
2
3
输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1

示例 2:

1
2
输入:coins = [2], amount = 3
输出:-1

示例 3:

1
2
输入:coins = [1], amount = 0
输出:0

提示:

1
2
3
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

2. answers

这道题显然是一道完全背包问题,但是优化目标是元素个数最小值。因此需要设置数组dp[j],保存在当前元素及其前面元素的基础上,在当前容量J下,所能达到总和为J的最小个数。

这道题,最开始想的是,和原来的问题一样,按步骤来就行,因为题目要求,没有结果返回-1,所以初始化数组为-1。并且对于装第一个元素,进行初始化。因为初始化为-1,导致下面的比较十分麻烦。

这里需要注意,递推公式仍然是取决于当前元素到底装不装。有以下几个要点:

  1. 如果不能够装,那么保持原状即可,即上一个元素的当前状态;
  2. 如果能装,并且装该元素:
    1. 如果装,而且回退到的那个空间dp[j-coins[i]]有结果,此时结果数+1;
    2. 如果装,但是回退到的那个空间dp[j-coins[i]]没有结果,显然,加上本数也无法满足要求,因此此时结果数为判断是否能够整除本元素【j % coins[i]】,如果能整除,那么就是【j / coins[i]】,如果不能整除,那么就是-1;
  3. 如果能装但不装,所以,此时,也是保持上一个状态【注意,在比较取最小值的时候,注意,上一个状态是不是没结果】。
  4. 此时,对于23情况,则对比取最小值即可。

在取最小值的时候,需要注意【因为-1这里表示没有结果,而又因为取最小值,所以导致-1和最小值造成了冲突,比较麻烦】:

  1. 在比较23的最小值的时候,一定注意23是不是-1,如果是-1,就不用比较了,取值为不是-1的结果即可。
  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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class Solution_0126_02 {

public int coinChange(int[] coins, int amount) {

// 在当前元素的基础上,当容量为J时,且组合总和为J时的最小元素个数
int[] dp = new int[amount + 1];

Arrays.fill(dp, -1);

// 初始化,
for (int i = 0; i < dp.length; i++) {
if(i % coins[0] == 0) dp[i] = i / coins[0];
}

dp[0] = 0;

// 动态规划
for (int i = 1; i < coins.length; i++) {

for (int j = 0; j < dp.length; j++) {

// 如果能装,并且该值有结果,并且本值原来不是-1
if(j >= coins[i] && dp[j-coins[i]] != -1 && dp[j] != -1) dp[j] = Math.min(dp[j], dp[j-coins[i]] + 1);

// 如果能装,并且该值有结果,并且本值原来是-1
else if(j >= coins[i] && dp[j-coins[i]] != -1 && dp[j] == -1) dp[j] = dp[j-coins[i]] + 1;

// 如果能装,但是该值没结果,且本值为-1,显然判断能否只装这一个。
else if(j >= coins[i] && dp[j] == -1) dp[j] = j % coins[i] == 0 ? j / coins[i] : -1;

// 如果能装,但是该值没结果,且本值不为-1,显然判断能否只装这一个,如果不能装本值,显然就是原来值;否则取最小值。
else if(j >= coins[i] && dp[j] != -1) {

int temp = j % coins[i] == 0 ? j / coins[i] : -1;
if(temp != -1)
dp[j] = Math.min(temp, dp[j]);
}
}
}

return dp[amount];
}

public static void main(String[] args) {
System.out.println();

Solution_0126_02 s = new Solution_0126_02();

// int[] coins = {1, 2, 5};
// int amount = 11;

// int[] coins = {1};
// int amount = 0;

// int[] coins = {2};
// int amount = 3;

int[] coins = {2, 5, 10, 1};
int amount = 27;

System.out.println(s.coinChange(coins, amount));
}
}

后续参考了题解,上面的问题在于-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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public class Solution_0126 {

public int coinChange(int[] coins, int amount) {

int max = Integer.MAX_VALUE;
int[] dp = new int[amount + 1];

//初始化dp数组为最大值
for (int j = 0; j < dp.length; j++) {
dp[j] = max;
}

//当金额为0时需要的硬币数目为0
dp[0] = 0;

// 动态规划,外层遍历背包容量,内层遍历物品
// 当前元素的取值取决于:(如果不能装本物品,那么就保持原状即可)(如果能装下本物品,那么就对比装和不装,取最小值)
// TODO 因为装的话,肯定需要回退到足够的空间那里,所以只有哪个空间是有结果的时候,才应该装。(如果没有结果,显然本次就不应该装)
// 而不装,也就是保持原状。
// TODO 因此,【只有能装(注意0也是能装),并且回退的那里有结果】,才比较装和不装。
for (int i = 0; i < coins.length; i++) {

// 正序遍历:完全背包每个硬币可以选择多次
for (int j = coins[i]; j <= amount; j++) {

// 只有dp[j-coins[i]]不是初始最大值时,该位才有选择的必要
// 不是最大值,即能装
if (dp[j - coins[i]] != max) {
//选择硬币数目最小的情况
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
}

// 即使是最大值,那么可不可以完全装自身呢?
// 其实是没必要的,因为 如果 j 能够整除 coins[i],显然在首次即[0+coins[i]]时,就已经满足上面的if判断了。
// 因此,后续的所有整除coins[i]的都满足上述要求。
}

}

return dp[amount] == max ? -1 : dp[amount];
}

public static void main(String[] args) {
System.out.println();

Solution_0126 s = new Solution_0126();

// int[] coins = {1, 2, 5};
// int amount = 11;

// int[] coins = {1};
// int amount = 0;

// int[] coins = {2};
// int amount = 3;

int[] coins = {2, 5, 10, 1};
int amount = 27;

System.out.println(s.coinChange(coins, amount));
}
}

3. 备注

参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)代码随想录 (programmercarl.com)


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