Java减治算法实现n枚硬币问题的代码,代码中出现元素相加和比较的语句
时间: 2024-02-15 16:01:55 浏览: 72
n枚硬币问题
下面是使用减治算法实现n枚硬币问题的Java代码,其中包含了元素相加和比较的语句:
```
public class CoinChange {
public int coinChange(int[] coins, int amount) {
if (amount < 1) {
return 0;
}
return coinChange(coins, amount, new int[amount]);
}
private int coinChange(int[] coins, int rem, int[] count) {
if (rem < 0) {
return -1;
}
if (rem == 0) {
return 0;
}
if (count[rem - 1] != 0) {
return count[rem - 1];
}
int min = Integer.MAX_VALUE;
for (int coin : coins) {
int res = coinChange(coins, rem - coin, count);
if (res >= 0 && res < min) {
min = 1 + res;
}
}
count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
return count[rem - 1];
}
}
```
在该代码中,我们使用了一个 `coinChange` 函数来计算使用给定的硬币数量,能够凑出指定金额的最少硬币数。这个函数内部调用了一个辅助函数 `coinChange`,它使用一个 `count` 数组来缓存已经计算过的金额,避免重复计算。
在 `coinChange` 函数中,我们使用了一个 `for` 循环来遍历所有硬币,并在每次迭代中调用 `coinChange` 函数来计算剩余金额所需的最少硬币数。如果当前硬币可以被使用,并且使用它所需的最少硬币数比之前计算过的最少硬币数还要少,那么就更新最少硬币数。
最后,我们将计算得到的最少硬币数存入 `count` 数组中,并返回该值。如果无法使用硬币凑出指定金额,则返回 `-1`。
阅读全文