凑零钱问题动态规划java

凑零钱问题是指给定一定面额的硬币，以及一个总金额，求出能够凑出该总金额的最少硬币数。这是一个经典的动态规划问题，可以使用Java语言来实现。

首先，我们需要定义一个函数来解决凑零钱问题。该函数需要接收两个参数：硬币面额数组和目标金额。函数的返回值应该是能够凑出目标金额的最少硬币数。

接下来，我们可以使用一个一维数组来记录每个金额所需要的最少硬币数。数组的长度应该是目标金额加一，因为我们需要计算从0到目标金额的最少硬币数。

然后，我们可以使用一个循环来遍历每个金额，并计算出凑出该金额所需要的最少硬币数。具体的计算方法是：对于每个硬币面额，如果该面额小于等于当前金额，那么就可以使用该硬币来凑出当前金额。此时，我们需要使用之前计算出的最少硬币数来更新当前金额所需要的最少硬币数。具体的更新方法是：将当前金额减去硬币面额，然后加上使用该硬币所需要的最少硬币数。最后，我们需要在所有硬币面额中选择最小的硬币数作为当前金额所需要的最少硬币数。

最后，我们可以返回数组中最后一个元素作为凑出目标金额的最少硬币数。

下面是Java代码实现：

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < coins.length; j++) {
            if (coins[j] <= i) {
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}