用java实现最少硬币问题_最少硬币数——Java

最少硬币问题是指在给定面额的硬币中，找出能够组成指定金额的最少硬币数。可以使用动态规划来解决这个问题。

以下是用Java实现最少硬币问题的示例代码：

public class MinimumCoins {
    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 && 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 = {1, 2, 5};
        int amount = 11;
        int minCoins = minCoins(coins, amount);
        System.out.println("Minimum coins required to make " + amount + " is " + minCoins);
    }
}

在上面的代码中，我们使用一个数组dp来存储每个金额所需的最少硬币数。我们首先将dp数组初始化为Integer.MAX_VALUE，然后将dp[0]设置为0，因为组成0元需要0枚硬币。

接下来，我们使用两个嵌套循环来遍历每个金额和每个硬币面额。如果当前硬币面额小于等于当前金额，并且使用当前硬币面额可以组成金额i - coins[j]，那么我们更新dp[i]为dp[i - coins[j]] + 1的最小值。最终，dp[amount]存储了组成指定金额所需的最少硬币数。如果dp[amount]等于Integer.MAX_VALUE，则表示无法组成指定金额，返回-1。

在上面的示例中，我们使用coins数组存储硬币面额，amount变量存储指定金额。输出结果为“Minimum coins required to make 11 is 3”，表示组成11元需要3枚硬币，即1枚5元硬币和2枚2元硬币。