LeetCode_126_CoinChange

LeetCode
发布日期:   2022-06-22
更新日期:   2022-06-22
文章字数:   1.7k
阅读时长:   7 分
阅读次数:  

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

文章作者: 浮云
文章链接: https://ihianian.github.io/2022/06/22/LeetCode-126-CoinChange/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
LeetCode
赏
  目录