LeetCode322-零钱兑换

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/coin-change/

中文链接：https://leetcode-cn.com/problems/coin-change/

题目详述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

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

示例 2:

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

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

题目详解

完全背包问题。

  • 相当于由 n 种物品，每种物品的体积是硬币面值，价值是 1，求恰好装满背包最少需要多少价值的物品。
  • dp[i] 表示凑成金额 i 最少需要多少个硬币。
  • 外层循环枚举金额 i ，内层循环枚举硬币 coin，则 dp[i] = min{dp[i], dp[i - coin] + 1}。
  • 注意 dp 数组正确的初始化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode_00322 {

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        // 初始化 dp
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int coin : coins) {
                if (i >= coin) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] != amount + 1 ? dp[amount] : -1;
    }
}

完全背包更好的书写方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class LeetCode_00322 {

    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        // 恰好初始化 dp[0] = 0, 其余为无穷
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int coin : coins) {
            for (int i = coin; i <= amount; ++i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] != amount + 1 ? dp[amount] : -1;
    }
}