用java写一个动态规划求最少纸币数

以下是用Java实现动态规划求解最少纸币数的示例代码：

import java.util.Arrays;

public class MinCoins {
    public static int minCoins(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];
    }

    public static void main(String[] args) {
        int[] coins = {1, 5, 10, 20, 50};
        int amount = 65;
        int minCoins = minCoins(coins, amount);
        System.out.println("最少需要 " + minCoins + " 张纸币");
    }
}

在上面的代码中，我们定义了一个minCoins()方法来计算最少需要多少张纸币才能凑出指定金额。该方法接受两个参数：纸币面额数组和目标金额。我们首先初始化一个长度为amount+1的dp数组，并将其所有元素初始化为amount+1。我们将dp[0]初始化为0，因为凑出0元需要0张纸币。

接下来，我们使用两个for循环来填充dp数组。外部循环控制金额，内部循环控制纸币面额。对于每个金额i，我们遍历所有的纸币面额，并计算使用该面额所需的最少纸币数。我们使用dp[i-coins[j]] + 1来更新dp[i]的值，其中coins[j]表示当前纸币面额。

最后，我们返回dp[amount]的值，如果其大于amount，则表示无法凑出指定金额，返回-1即可。

在示例代码中，我们使用了一个包含1、5、10、20和50的纸币面额数组，并尝试凑出65元。输出结果为“最少需要 3 张纸币”，即需要一张50元、一张10元和一张5元纸币。