最少硬币 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 (coins[j] <= i) {
                int sub_res = dp[i - coins[j]];
                if (sub_res != Integer.MAX_VALUE && sub_res + 1 < dp[i]) {
                    dp[i] = sub_res + 1;
                }
            }
        }
    }
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}

其中，coins 表示硬币的面额数组，amount 表示需要找零的金额。dp 数组表示找零所需的最少硬币数量，dp[i] 表示找零 i 元所需的最少硬币数量。

算法的核心是两层循环，外层循环遍历需要找零的金额，内层循环遍历硬币面额数组。对于每个需要找零的金额，我们都遍历一遍硬币面额数组，找到小于等于该金额的面额，然后计算出剩余金额所需的最少硬币数量，并取最小值。最终，dp[amount] 就是所需的最少硬币数量。

需要注意的是，如果无法找零，则返回 -1。