这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数,一般而言有多种方式。例如:给定了6种钱币面值为2、5、10、20、50、100,用来凑15元,可以用5个2元、1个5元,或者3个5元,或者1个5元、1个10元,等等。显然,最少需要2个钱币才能凑成15元。 你的任务就是,给定若干个互不相同的钱币面值,编程计算,最少需要多少个钱币才能凑成某个给出的钱数。。java
时间: 2024-03-06 16:52:22 浏览: 179
最少钱币问题
4星 · 用户满意度95%
好的,这是一个经典的动态规划问题,可以使用贪心算法或动态规划算法来解决。我来给你提供一个动态规划的解决方案,Java代码如下:
```java
public static int minCoins(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i && dp[i - coins[j]] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
```
其中,`coins`是给定的钱币面值数组,`amount`是要凑成的钱数。我们使用一个数组`dp`来记录每个钱数最少需要多少个钱币才能凑成。初始化时,将`dp[0]`设为0,其他的都设为最大值,表示无法凑成。然后,我们遍历从1到amount的每个钱数,对于每个钱数,遍历所有的钱币面值,如果当前钱币面值小于等于当前钱数,且当前钱数减去当前钱币面值所需的最少钱币数不为无穷大,则更新`dp[i]`为两者之间的较小值。最后,返回`dp[amount]`即可。
需要注意的是,如果最终`dp[amount]`为最大值,则说明无法凑成该钱数,返回-1即可。
阅读全文