322. 零钱兑换

这是经典的 动态规划（Dynamic Programming） 问题，称为 “零钱兑换”（Coin Change）。

🔍 问题分析

• 给定硬币面额数组 coins 和目标金额 amount
• 每种硬币可以无限使用
• 要求：凑出 amount 所需的 最少硬币数
• 若无法凑出，返回 -1

✅ 解题思路：动态规划

我们定义一个数组 dp，其中：

• dp[i] 表示凑出金额 i 所需的最少硬币数
• 初始时，dp[0] = 0（凑 0 元需要 0 个硬币）
• 其他位置初始化为 amount + 1（或 Integer.MAX_VALUE），表示暂时不可达

状态转移方程：

dp[i] = min(dp[i], dp[i - coin] + 1)   // 对每个 coin ∈ coins，且 coin ≤ i

最后，如果 dp[amount] > amount，说明无法凑出，返回 -1；否则返回 dp[amount]

💡 Java 实现

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        
        int[] dp = new int[amount + 1];
        // 初始化为 amount + 1（代表无穷大，因为最多用 amount 个 1 元硬币）
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
}

⏱️ 时间 & 空间复杂度

• 时间复杂度：O(amount × coins.length)
• 空间复杂度：O(amount)