当前位置：首页 > ds >正文

LeetCode Hot100刷题——零钱兑换

ds 2025/7/27 20:56:38

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

解题思路

本题是一个典型的动态规划问题，属于完全背包问题的应用。目标是使用最少数量的硬币凑出给定的总金额。每种硬币的数量是无限的，因此可以重复使用同一面额的硬币。

核心思路

状态定义：定义dp[i] 表示凑成金额 i 所需的最少硬币个数。
初始化：dp[0] = 0（凑成0元不需要硬币），其他位置初始化为一个较大的值（例如 amount + 1），表示无法凑出。
状态转移：对于每个金额 i （从1到 amount），遍历每个硬币面额coin：
1. 如果coin <= i，说明可以使用这枚硬币，则更新dp[i] = min[dp[i], dp[i - coin] + 1]。
结果判断：如果dp[amount] 仍为初始值（大于amount），说明无法凑出，返回 -1，否则返回 dp[amount]。

优化点

初始化值选择：使用 amount + 1 作为不可达标记，因为最多使用 amount 枚硬币（全用1元硬币）。
提前处理无法凑出的情况：当所有硬币面额都大于目标金额时，直接返回 -1（但动态规划过程已涵盖此情况，可不单独处理）。

程序代码

class Solution {public int coinChange(int[] coins, int amount) {// 处理金额为0的情况if(amount == 0){return 0;}// 创建dp数组并初始化为一个较大的值（amount + 1）int[] dp = new int[amount + 1];Arrays.fill(dp, amount + 1);dp[0] = 0;// 动态规划，金额从1到amountfor(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 × n)，其中 n 是硬币种类数。外层循环遍历 amount 次，内层循环遍历所有硬币。
空间复杂度：O(amount)，用于存储 dp 数组。

示例验证

示例 1：coins = [1, 2, 5], amount = 11
- dp[11] 的计算过程：
  - dp[1] = 1（1元硬币）
  - dp[2] = min(dp[2], dp[0] + 1) = 1（2元硬币）
  - dp[5] = 1（5元硬币）
  - dp[11] = min(dp[11], dp[10] + 1) → dp[10] = 2（两个5元），最终 dp[11] = 3（5元 + 5元 + 1元）。
- 输出：3，符合预期。
示例 2：coins = [2], amount = 3
- dp[1] 无法更新（保持初始值 4）
- dp[3] = min(dp[3], dp[1] + 1) → dp[1] 不可达，因此 dp[3] 保持初始值 4（大于3），返回 -1。
- 输出：-1，符合预期。
示例 3：coins = [1], amount = 0
- 直接返回0（代码开头特判）。
- 输出：0，符合预期。