给你一个整数数组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 <= 121 <= coins[i] <=0 <= amount <=
解题思路（动态规划）
- 定义状态：设
dp[i]表示 “凑成金额i所需的最少硬币数”。 - 初始化：
- 初始化
dp数组长度为amount + 1，值为amount + 1（因为最多需要amount个 1 元硬币，用amount + 1表示 “无法凑成”）； - 令
dp[0] = 0（凑成金额 0 不需要硬币）。
- 初始化
- 状态转移：
- 遍历每个金额
i（从 1 到amount）； - 对每个硬币
coin，若coin ≤ i，则dp[i] = min(dp[i], dp[i - coin] + 1)（选当前硬币时，硬币数 = 凑成i-coin的最少硬币数 + 1）。
- 遍历每个金额
- 结果判断：若
dp[amount]仍为初始值amount + 1，说明无法凑成，返回-1；否则返回dp[amount]。
Python代码：
from typing import List class Solution: def coinChange(self, coins: List[int], amount: int) -> int: """ 零钱兑换问题：计算凑成指定金额所需的最少硬币数 :param coins: 可用的硬币面额列表（非负整数，无重复） :param amount: 目标凑单金额（非负整数） :return: 最少硬币数；若无法凑成返回-1 """ # 边界条件1：目标金额为0，无需硬币 if amount == 0: return 0 # 边界条件2：硬币列表为空 或 所有硬币面额都大于目标金额，无法凑成 if not coins or min(coins) > amount: return -1 # 初始化dp数组：dp[i]表示凑成金额i所需的最少硬币数 # 初始值设为amount+1（最大可能需要amount个1元硬币，用amount+1标记"无法凑成"） dp = [amount + 1] * (amount + 1) dp[0] = 0 # 基准：凑成金额0需要0个硬币 # 优化：对硬币排序，遇到大于当前金额的硬币可提前终止内层循环 coins.sort() # 遍历每个金额（从1到目标金额） for i in range(1, amount + 1): # 遍历每个硬币面额 for coin in coins: # 若当前硬币面额大于当前金额，后续硬币更大，直接break if coin > i: break # 状态转移：选当前硬币时，硬币数=凑成i-coin的最少硬币数+1 dp[i] = min(dp[i], dp[i - coin] + 1) # 最终判断：若dp[amount]仍为初始值，说明无法凑成；否则返回最少硬币数 return dp[amount] if dp[amount] != amount + 1 else -1 # ------------------- 测试用例 ------------------- if __name__ == "__main__": solution = Solution() # 测试用例1：常规可凑成（示例1） coins1 = [1, 2, 5] amount1 = 11 print(f"测试用例1：coins={coins1}, amount={amount1}") print(f"最少硬币数：{solution.coinChange(coins1, amount1)}") # 预期输出：3（5+5+1） # 测试用例2：无法凑成（示例2） coins2 = [2] amount2 = 3 print(f"\n测试用例2：coins={coins2}, amount={amount2}") print(f"最少硬币数：{solution.coinChange(coins2, amount2)}") # 预期输出：-1 # 测试用例3：金额为0（示例3） coins3 = [1] amount3 = 0 print(f"\n测试用例3：coins={coins3}, amount={amount3}") print(f"最少硬币数：{solution.coinChange(coins3, amount3)}") # 预期输出：0 # 测试用例4：硬币面额无序 + 大额金额 coins4 = [10, 5, 1, 25] amount4 = 41 print(f"\n测试用例4：coins={coins4}, amount={amount4}") print( f"最少硬币数：{solution.coinChange(coins4, amount4)}") # 预期输出：3（25+10+5+1 → 修正：25+10+5+1=41？不，25+10+5+1是4个，正确最优是25+10+5+1 或 10*4+1，实际最优是 25+10+5+1=41（4个），代码会返回4）LeetCode提交代码：
class Solution: def coinChange(self, coins: List[int], amount: int) -> int: # 初始化dp数组，默认值为“无法凑成”的标记（amount+1） dp = [amount + 1] * (amount + 1) dp[0] = 0 # 凑成金额0需要0个硬币 # 遍历每个金额 for i in range(1, amount + 1): # 遍历每个硬币 for coin in coins: if coin <= i: # 更新最少硬币数 dp[i] = min(dp[i], dp[i - coin] + 1) # 判断结果：若dp[amount]未被更新，说明无法凑成 return dp[amount] if dp[amount] != amount + 1 else -1程序运行结果展示
测试用例1：coins=[1, 2, 5], amount=11 最少硬币数：3 测试用例2：coins=[2], amount=3 最少硬币数：-1 测试用例3：coins=[1], amount=0 最少硬币数：0 测试用例4：coins=[10, 5, 1, 25], amount=41 最少硬币数：4总结
本文探讨了使用动态规划解决零钱兑换问题。给定不同面额的硬币数组coins和目标金额amount，需计算凑成金额的最少硬币数，若无法凑成则返回-1。核心思路是通过动态规划数组dp记录每个金额的最小硬币数，初始化dp[0]=0，其他为amount+1（表示不可达）。遍历金额时，对每个硬币面额进行状态转移：dp[i] = min(dp[i], dp[i-coin]+1)。最终检查dp[amount]是否被更新，未更新则返回-1。Python代码实现并通过测试用例验证，如示例coins=[1,2,5]和amount=11输出3（5+5+1）。算法时间复杂度为O(amount×n)，其中n为硬币种类数。
