假如有 2 块,3 块,7 块面额的纸币,如何使用最小的纸币数量来凑成 100 块。编程题 java
时间: 2024-03-13 14:45:50 浏览: 67
可以使用动态规划的思想来解决此问题。首先定义一个数组 `dp[i]` 表示凑成金额为 `i` 时所需的最小纸币数量。初始时,`dp[0] = 0`,因为凑成金额为 0 不需要任何纸币。
接下来从金额为 1 开始遍历到 100,对于每个金额,遍历所有可能的纸币面额,更新 `dp` 数组。具体来说,对于每个面额 `j`,如果 `i >= j`,则可以使用一张面额为 `j` 的纸币,然后需要凑成金额为 `i-j`,此时所需的最小纸币数量为 `dp[i-j]`,因此总的最小纸币数量为 `dp[i-j] + 1`。如果这个值比当前的 `dp[i]` 更小,则更新 `dp[i]`。最后 `dp[100]` 就是凑成 100 块所需的最小纸币数量。
以下是 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 (i >= coins[j] && 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];
}
public static void main(String[] args) {
int[] coins = {2, 3, 7};
int amount = 100;
System.out.println(minCoins(coins, amount)); // output: 15
}
```
阅读全文