零钱兑换

难度:

标签:

题目描述

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

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 2³¹ - 1
0 <= amount <= 10⁴

代码结果

运行时间: 1336 ms, 内存: 14.9 MB

/*
 * 思路：
 * 使用 Java Stream 和动态规划来解决问题。
 * 与传统的动态规划解法类似，创建一个 dp 数组并初始化。
 * 通过 IntStream 生成一个范围，并使用 mapToInt 方法来更新 dp 数组。
 */
 
import java.util.stream.IntStream;
 
public int coinChange(int[] coins, int amount) {
    if (amount == 0) return 0;
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1); // 初始化为最大值
    dp[0] = 0;
    IntStream.rangeClosed(1, amount).forEach(i -> {
        dp[i] = IntStream.of(coins)
                .filter(coin -> i >= coin)
                .map(coin -> dp[i - coin] + 1)
                .min()
                .orElse(dp[i]);
    });
    return dp[amount] > amount ? -1 : dp[amount];
}

解释

方法:

这个题解使用了动态规划的方法来解决零钱兑换问题。主要思路是：对于给定的总金额 amount，计算凑成该金额所需的最少硬币数量。定义 dp[i] 表示凑成金额 i 所需的最少硬币数量。对于每个金额 i，遍历所有可用硬币面额 coin，尝试使用该面额的硬币，并将所需硬币数量更新为 dp[i] 和 1 + dp[i-coin] 中的较小值。最终 dp[amount] 即为凑成总金额所需的最少硬币数量。

时间复杂度:

O(amount * len(coins))

空间复杂度:

O(amount)

代码细节讲解

🦆

为什么在初始化dp数组时，所有元素的初始值设置为amount+1而不是其他值？

▷

在初始化dp数组时，所有元素的初始值设置为amount+1，这是因为amount+1代表一个比任何实际需要的硬币数都大的值，实际上是一个无效值或无法达到的值。使用这样的值可以方便地在后续的动态规划过程中通过比较来更新最小硬币数。如果我们使用其他更小的值，可能导致无法正确反映凑成某金额需要的真实硬币数量。设置为amount+1就是为了确保dp[i]只有在找到有效的硬币组合时才被更新。

🦆

在题解中提到的`base case`是dp[0] = 0，请问为什么凑成金额0的硬币数需要设置为0？

▷

凑成金额0的硬币数需要设置为0是因为，如果不需要任何金额，自然也就不需要任何硬币。这是动态规划解决问题的基础情况，即‘base case’。设置dp[0] = 0是为了在开始动态规划时有一个正确的起点，因为凑成任何正金额至少需要一枚硬币，而凑成0金额则不需要任何硬币。

🦆

题解中提到如果dp[amount]的值等于amount+1，则返回-1，这个判断条件是如何确保无法凑成总金额时才触发的？

▷

如果dp[amount]的值等于amount+1，返回-1是因为amount+1是一个初始化时设置的无效值，如果在动态规划的过程中这个值没有被更新，说明没有找到任何有效的硬币组合来凑成该金额。这种情况下，dp[amount]保持为amount+1意味着凑成总金额amount是不可能的，因此返回-1来表示无法凑成指定金额。

🦆

在动态规划的更新公式中，为什么选择使用1 + dp[i-coin]来更新dp[i]？这里的1代表什么意义？

▷

在动态规划的更新公式中，使用1 + dp[i-coin]来更新dp[i]是因为这里的1代表使用了一枚当前遍历到的coin硬币。dp[i-coin]代表在使用这枚硬币之前，凑成金额i-coin所需的最少硬币数量。因此1 + dp[i-coin]就是加上这枚硬币之后，总的硬币数量。选择这种更新方式是为了确保每一步都考虑到使用每一种可能的硬币，从而找出凑成金额i的最少硬币数。

相关问题

最低票价

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

火车票有 三种不同的销售方式 ：

一张 为期一天 的通行证售价为 costs[0] 美元；
一张 为期七天 的通行证售价为 costs[1] 美元；
一张 为期三十天 的通行证售价为 costs[2] 美元。

通行证允许数天无限制的旅行。例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。

示例 1：

输入：days = [1,4,6,7,8,20], costs = [2,7,15]
输出：11
解释： 
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。
在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。
在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。
你总共花了 $11，并完成了你计划的每一天旅行。

示例 2：

输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
输出：17
解释：
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划： 
在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, ..., 30 天生效。
在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。 
你总共花了 $17，并完成了你计划的每一天旅行。

提示：

1 <= days.length <= 365
1 <= days[i] <= 365
days 按顺序严格递增
costs.length == 3
1 <= costs[i] <= 1000

列举单词的全部缩写无向图中连通分量的数目