当前位置：首页 > Java

java 如何找零

2026-03-20 18:07:47Java

找零问题的解决方案

找零问题是一个经典的算法问题，通常涉及给定一定金额的钱和不同面额的硬币，计算出如何用最少数量的硬币来凑出该金额。以下是几种常见的解决方案。

贪心算法

贪心算法是一种直观的解决方案，每次选择当前最大面额的硬币，直到凑足金额。这种方法在某些情况下有效，但不适用于所有面额组合。

java 如何找零

public static int[] greedyChange(int amount, int[] coins) {
    Arrays.sort(coins); // 确保硬币面额从小到大排序
    int[] result = new int[coins.length];
    for (int i = coins.length - 1; i >= 0; i--) {
        result[i] = amount / coins[i];
        amount %= coins[i];
    }
    return result;
}

动态规划

动态规划是解决找零问题的更通用方法，可以处理所有面额组合。通过构建一个数组来记录每个金额所需的最小硬币数。

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 coin : coins) {
        for (int i = coin; i <= amount; i++) {
            if (dp[i - coin] != Integer.MAX_VALUE) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}

递归方法

递归方法虽然直观，但效率较低，适合小规模问题或作为教学示例。

public static int recursiveChange(int amount, int[] coins) {
    if (amount == 0) return 0;
    int minCoins = Integer.MAX_VALUE;
    for (int coin : coins) {
        if (coin <= amount) {
            int subResult = recursiveChange(amount - coin, coins);
            if (subResult != Integer.MAX_VALUE && subResult + 1 < minCoins) {
                minCoins = subResult + 1;
            }
        }
    }
    return minCoins;
}

使用示例

以下是如何调用上述方法的示例代码：

public static void main(String[] args) {
    int[] coins = {1, 5, 10, 25};
    int amount = 36;
    System.out.println("Minimum coins needed: " + minCoins(coins, amount));
    int[] change = greedyChange(amount, coins);
    System.out.println("Greedy change: " + Arrays.toString(change));
}