动态规划求零钱兑换最少硬币数：定义dp[i]为凑出金额i的最少硬币数，dp[0]=0，其余初始化为amount+1；对每个i遍历硬币，若i≥coin则dp[i]=min(dp[i], dp[i-coin]+1)；最终dp[amount]>amount时返回-1。
用动态规划解决零钱兑换最少硬币数问题，核心是定义状态、写出状态转移方程，并合理初始化。它不是暴力尝试所有组合，而是从小面额开始逐步构建出凑成每个金额所需的最少硬币数。
明确状态定义和 base case
设 dp[i] 表示凑出金额 i 所需的最少硬币个数。目标是求 dp[amount]。
初始时：
- dp[0] = 0（凑 0 元不需要任何硬币）
- 其余位置可初始化为一个较大值（如 amount + 1 或 Integer.MAX_VALUE），表示“暂时不可达”
写出状态转移方程
对每个金额 i（从 1 到 amount），遍历所有硬币 coin：
- 如果 i >= coin，说明当前硬币能用
- 则尝试用这枚硬币：凑出 i - coin 最少要 dp[i - coin] 个，再加 1 枚当前硬币 → 候选值为 dp[i - coin] + 1
- 取所有可行 coin 对应的最小值：dp[i] = min(dp[i], dp[i - coin] + 1)
注意边界与不可解情况
最终若 dp[amount] 仍为初始大值（比如 > amount），说明无法凑出，返回 -1。
常见易错点：
- 初始化不能全设为 0 或 -1，否则干扰最小值更新
- 内层循环中必须检查 i >= coin，避免数组越界
- 硬币数组可能无序，但不影响逻辑；无需排序
代码结构示意（Java）
关键逻辑简洁清晰：
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); // 不可达的标记
dp[0] = 0;
<p>for (int i = 1; i = coin) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}</p><p>return dp[amount] > amount ? -1 : dp[amount];</p>时间复杂度 O(amount × coins.length)，空间复杂度 O(amount)。不复杂但容易忽略初始化和边界判断。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
