零钱兑换
Coin Change
本机进度仅保存在当前浏览器
题目描述
给你一个整数数组 coins 表示不同面额的硬币，以及一个整数 amount 表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数；任何硬币组合都无法凑出总金额则返回 -1。每种硬币数量无限。
示例：coins = [1, 2, 5]，amount = 11，输出 3（5 + 5 + 1）。
解题思路
- 完全背包的"最少件数"版本：dp[x] 表示凑出金额 x 的最少硬币数，答案 dp[amount]。
- 转移：枚举每种硬币 c，dp[x] = min(dp[x - c] + 1)，含义是"最后用一枚 c"。
- 初始化 dp[0] = 0、其余为正无穷表示不可达；外层枚举金额、内层枚举硬币的顺序均可（求最少件数与组合/排列无关）。
参考实现
查看参考实现Python · 建议先自行作答
def coinChange(coins, amount):
INF = amount + 1 # 正无穷哨兵
dp = [0] + [INF] * amount
for x in range(1, amount + 1):
for c in coins:
if c <= x:
dp[x] = min(dp[x], dp[x - c] + 1)
return -1 if dp[amount] > amount else dp[amount]