最少硬币问题java

最少硬币问题，也称为找零问题，是一个经典的计算机科学算法问题，通常涉及给定一组货币面额，计算出最小的组合数以达到某个特定金额。在 Java 中，这个问题可以使用动态规划方法解决。

例如，如果我们有硬币面额为 [1, 5, 10] 分，那么给定目标金额 17 分，我们需要找出最少需要多少枚硬币才能凑够这个金额。这可以通过创建一个数组 `dp` 来记录每个金额下所需的最少数量的硬币：

public int minCoins(int[] coins, int amount) {
    // 初始化 dp 数组，所有值设为 Integer.MAX_VALUE
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    
    // 设置基础状态，0分不需要硬币
    dp[0] = 0;
    
    for (int coin : coins) {
        // 遍历每种硬币，如果当前硬币能覆盖到dp[i]金额，则更新dp[i+coin]
        for (int i = coin; i <= amount; i++) {
            if (dp[i - coin] != Integer.MAX_VALUE && dp[i] > dp[i - coin] + 1) {
                dp[i] = dp[i - coin] + 1;
            }
        }
    }

    // 返回达到最大金额所需的最少硬币数，如果没有找到可行方案则返回-1 或者抛异常
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}