37.零钱兑换(题号：322)

public class CoinChange {
    // 动态规划
    public int coinChange(int[] coins, int amount){
        int n = coins.length;    // 硬币种类数

        // 定义dp数组，保存金额为i的对应最少硬币数为dp[i]
        int[] dp = new int[amount + 1];

        // 初始状态
        dp[0] = 0;

        // 遍历状态，依次转移
        for (int i = 1; i <= amount; i++){
            // 保留当前硬币的最小数量
            int minNum = Integer.MAX_VALUE;

            // 遍历所有可能的硬币面值，作为凑出i金额的最后一个硬币
            for (int coin: coins){
                // 必须coin不能超过i，并且i-coin的金额可以凑出来
                if (coin <= i && dp[i - coin] != -1){
                    minNum = Math.min(minNum, dp[i - coin] + 1);
                }
            }

            dp[i] = minNum == Integer.MAX_VALUE ? -1 : minNum;
        }

        return dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;

        CoinChange coinChange = new CoinChange();

        System.out.println(coinChange.coinChange(coins, amount));
    }
}