零钱兑换

/*
 * 思路：
 * 1. 使用动态规划的方法，定义一个 dp 数组，dp[i] 表示凑成金额 i 所需的最少硬币个数。
 * 2. 使用 IntStream 和 Arrays.stream 来实现动态规划的步骤。
 * 3. 初始化 dp[0] = 0，表示凑成金额 0 所需的硬币个数为 0。
 * 4. 对于每个金额 i，从 1 到 amount，尝试用每个硬币去更新 dp[i]。
 * 5. 如果当前硬币的面值不大于 i，则 dp[i] = Math.min(dp[i], dp[i - coin] + 1)。
 * 6. 最后，返回 dp[amount]，如果 dp[amount] 仍然是初始值，则返回 -1 表示无法凑成该金额。
 */
import java.util.*;
import java.util.stream.*;

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        IntStream.rangeClosed(1, amount).forEach(i -> {
            Arrays.stream(coins).forEach(coin -> {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            });
        });
        return dp[amount] > amount ? -1 : dp[amount];
    }
}