递归求解硬币兑换问题代码,代码用java表示
时间: 2023-07-09 22:31:25 浏览: 110
[6.3.1]--410找零兑换问题的递归解法.srt
好的,下面是使用 Java 表示递归求解硬币兑换问题的代码:
```java
public class CoinChange {
private static final int INF = Integer.MAX_VALUE;
public static int coinChange(int[] coins, int amount) {
if (amount == 0) {
return 0;
}
if (amount < 0) {
return INF;
}
int ans = INF;
for (int coin : coins) {
int curAns = coinChange(coins, amount - coin);
if (curAns == INF) {
continue;
}
ans = Math.min(ans, curAns + 1);
}
return ans;
}
public static void main(String[] args) {
int[] coins = {1, 2, 5};
int amount = 11;
int ans = coinChange(coins, amount);
System.out.println(ans);
}
}
```
在这个代码中,我们定义了一个静态方法 `coinChange`,该方法接受两个参数:硬币面值数组 `coins` 和需要凑出的金额 `amount`,返回值是凑出指定金额所需的最少硬币数量。在方法中,我们首先处理几种边界情况:如果 `amount` 等于 0,表示已经凑出了指定的金额,不需要再进行任何操作,返回 0;如果 `amount` 小于 0,表示当前的硬币面值无法凑出指定的金额,返回一个非常大的数,表示无法凑出。
接下来,我们对于每一种硬币面值,都可以选择使用或者不使用,分别递归计算使用和不使用的情况下所需的硬币数量,取其中的较小值即可。在递归过程中,我们还需要注意特判无法凑出指定金额的情况,避免出现无限递归的情况。最后,我们在 `main` 方法中对代码进行测试,验证其正确性。
阅读全文