用java代码实现X星最新版纸币的面额很奇怪,一共有1元、4元、9元、16元、25元、100元六种不同的面额。 已知每种面额纸币的数量不限,现在需要从中选取若干张纸币组成N元(N为正整数)。 请编写一个程序计算组成N元最少需要的纸币数量。
时间: 2024-05-03 16:18:22 浏览: 28
这道题可以使用动态规划来解决,设f[i]表示组成i元所需的最少纸币数量,则有状态转移方程:f[i] = min(f[i-1], f[i-4], f[i-9], f[i-16], f[i-25], f[i-100]) + 1。
其中,f[i-1]表示选取1元面额的纸币,f[i-4]表示选取4元面额的纸币,以此类推。最终的答案即为f[N]。
以下是Java代码实现:
```java
public class MinimumCoins {
public static int minCoins(int N) {
int[] f = new int[N+1];
Arrays.fill(f, Integer.MAX_VALUE);
f[0] = 0;
for (int i = 1; i <= N; i++) {
if (i >= 1) f[i] = Math.min(f[i], f[i-1] + 1);
if (i >= 4) f[i] = Math.min(f[i], f[i-4] + 1);
if (i >= 9) f[i] = Math.min(f[i], f[i-9] + 1);
if (i >= 16) f[i] = Math.min(f[i], f[i-16] + 1);
if (i >= 25) f[i] = Math.min(f[i], f[i-25] + 1);
if (i >= 100) f[i] = Math.min(f[i], f[i-100] + 1);
}
return f[N];
}
public static void main(String[] args) {
int N = 200;
System.out.println(minCoins(N));
}
}
```
输出结果为 2,表示组成200元最少需要的纸币数量为2张100元纸币。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)