Java 中使给定值达到最小硬币数

在本节中，我们将学习如何使用最少数量的硬币来兑换给定的金额。使用最少硬币兑换给定金额的问题是 硬币找零问题 的一个变体。

在这个问题中，给定了金额 Y。任务是找到兑换给定金额 Y 所需的最少硬币数量。硬币只能从给定的数组 C[] = {C1, C2, C3, C4, C5, …} 中选取。如果任何数量的硬币不适合兑换给定的金额，则显示相应的消息。

示例 1

输入: C[] = {5, 10, 25}, Y = 30

输出: 兑换金额 30 最少需要 2 枚硬币。

解释: 兑换金额 30 可能有多种硬币组合。

5 + 5 + 5 + 5 + 5 + 5 = 30 (硬币总数: 6)

5 + 5 + 5 + 5 + 10 = 30 (硬币总数: 5)

5 + 5 + 10 + 10 = 30 (硬币总数: 4)

10 + 10 + 10 = 30 (硬币总数: 3)

5 + 25 = 30 (硬币总数: 2)

因此，我们看到兑换金额 30 最少需要 2 枚硬币。所以，我们的答案是 2。

示例 2

输入

C[] = {4, 3, 2, 6}, Y = 15

输出: 兑换金额 15 最少需要 3 枚硬币。

解释: 兑换金额 12 可能有多种硬币组合。

2 + 2 + 2 + 2 + 2 + 2 + 3 = 15 (硬币总数: 7)

2 + 2 + 2 + 3 + 3 + 3 = 15 (硬币总数: 6)

2 + 2 + 2 + 2 + 3 + 4 = 15 (硬币总数: 6)

2 + 2 + 2 + 3 + 6 = 15 (硬币总数: 5)

3 + 3 + 3 + 3 + 3 = 15 (硬币总数: 5)

2 + 2 + 3 + 4 + 4 = 15 (硬币总数: 5)

3 + 3 + 3 + 6 = 15 (硬币总数: 4)

4 + 4 + 4 + 3 = 15 (硬币总数: 4)

2 + 3 + 4 + 6 = 15 (硬币总数: 4)

4 + 4 + 4 + 3 = 15 (硬币总数: 4)

6 + 6 + 3 = 15 (硬币总数: 3)

因此，我们看到兑换金额 15 最少需要 3 枚硬币。所以，我们的答案是 3。

问题解决方案

这个问题有多种解决方法。但在本节中，我们将通过以下两种方法来解决问题：

• 使用递归
• 使用动态规划

让我们逐一来看这些方法。

使用递归

使用以下递归公式可以解决给定的问题。

观察以下实现。

文件名: MinCoins.java

输出

For the sum 30
The minimum number of required coins is: 2
Using the following coins: 
5 10 25 

For the sum 15
The minimum number of required coins is: 3
Using the following coins: 
4 3 2 6

时间复杂度: 上述程序的运行时间复杂度是指数级的。

由于指数级的时间复杂度始终很高，因此需要降低时间复杂度。因此，我们需要一种优化的方法。以下实现展示了这一点。

使用动态规划

如果我们观察上述方法，有很多子问题被计算了不止一次。因此，优化是直接的。我们需要消除冗余子问题的额外计算时间。我们将在下面的程序中进行相同的操作。

文件名: MinCoins1.java

输出

For the sum 30
The minimum number of required coins is: 2
Using the following coins: 
5 10 25 

For the sum 15
The minimum number of required coins is: 3
Using the following coins: 
4 3 2 6

时间复杂度: 上述程序的运行时间复杂度主要取决于方法 minNoCoins() 中存在的嵌套 for 循环。由于内层 for 循环从 0 运行到 s，外层循环从 1 运行到 Y，因此时间复杂度为 O(sY)，其中 Y 是给定的金额，s 是硬币数组的大小。