题解 | #兑换零钱#

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        
        // 获取输入数据
        Scanner scan = new Scanner(System.in);
        String naim = scan.nextLine(); // 获取数组 arr 的长度和要找的钱数
        int n = Integer.valueOf(naim.split(" ")[0]); // 获取数组 arr 的长度
        int aim = Integer.valueOf(naim.split(" ")[1]); // 获取要找的钱数
        int[] coins = new int[n + 1]; // 定义一个整型数组，用于存放每种面值的货币
        String coinsString = scan.nextLine(); // 获取货币面值
        String[] consStrings = coinsString.split(" ");
        for (int i = 1; i <= n; i++) {
            coins[i] = Integer.valueOf(consStrings[i - 1]);
        }
        
        // 兑换零钱的动态规划的具体实现
        int[] dp = new int[aim + 1]; // 定义一个整型数组，用于存放需要找的钱数时，所需要的最少货币数
        Arrays.fill(dp, Integer.MAX_VALUE); // 初始化为 Integer.MAX_VALUE
        dp[0] = 0;
        for (int amount = 1; amount <= aim; amount++) {
            for (int coin : coins) {
                // 如果当前货币的面值大于要找的钱数，或者无法凑整
                if (coin > amount || dp[amount - coin] == Integer.MAX_VALUE) {
                    continue;
                }
                dp[amount] = Math.min(dp[amount - coin] + 1, dp[amount]);
            }
        }
        // 判断一下是否可以凑整，如果不可以凑整，直接返回 -1
        System.out.println(dp[aim] == Integer.MAX_VALUE ? -1 : dp[aim]);
    }
}