硬币问题解法 java

硬币问题通常是指给定一定面值的硬币和一个目标金额，从这些硬币中选择最少的硬币数量来凑出目标金额。以下是一种Java解法。

我们可以使用动态规划的思想来解决这个问题。假设给定硬币面值数组coins和目标金额amount，我们定义一个动态规划数组dp，其中dp[i]表示凑出金额i所需要的最少硬币数量。

首先，我们初始化dp数组为无穷大，并将dp[0]设为0，表示凑出金额0所需的硬币数量为0。
然后，我们遍历金额从1到目标金额amount的每个值。对于每个金额i，我们遍历硬币面值数组coins，如果硬币面值小于等于i，并且使用当前硬币面值凑出金额amount-i的数量dp[amount-i]加上当前硬币的数量1比dp[i]小的话，我们更新dp[i]为dp[amount-i]+1。
最终，我们返回dp[amount]即可得到凑出目标金额所需要的最少硬币数量。

下面是Java实现代码示例：

public class CoinChange {
    public int coinChange(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 coin : coins) {
                if (coin <= i && 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];
    }
}

以上就是使用Java解决硬币问题的一个简单实现。这段代码的时间复杂度为O(amount * n)，其中n是硬币面值的数量。