零钱兑换的最少硬币数

题目

零钱兑换的最少硬币数

信息

• 类型：问答
• 难度：⭐⭐

考点

动态规划,状态转移方程,边界条件处理,空间优化

快速回答

使用动态规划解决零钱兑换问题：

• 定义 dp[i] 表示组成金额 i 所需的最少硬币数
• 初始化 dp[0] = 0，其他为极大值（如 amount+1）
• 状态转移方程：dp[i] = min(dp[i], dp[i - coin] + 1)
• 遍历所有金额（1 到 amount）和所有硬币面额
• 最终结果：若 dp[amount] 未更新则返回 -1，否则返回 dp[amount]

问题描述

给定不同面额的硬币数组 coins 和一个总金额 amount，计算凑成总金额所需的最少硬币个数。每种硬币数量无限，若无法凑出则返回 -1。

示例：
输入：coins = [1, 2, 5], amount = 11
输出：3（5+5+1）

原理说明

本质是完全背包问题：

• 最优子结构：金额 i 的最优解依赖于 i - coin 的子问题最优解
• 重叠子问题：不同金额的计算存在大量重复子问题
• 状态定义：dp[i] 表示组成金额 i 的最小硬币数

代码示例（Python）

def coinChange(coins, amount):
    dp = [amount + 1] * (amount + 1)
    dp[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)

    return dp[amount] if dp[amount] <= amount else -1

最佳实践

• 初始化技巧：用 amount+1 代替正无穷，便于最终判断
• 遍历顺序：先遍历金额再遍历硬币（排列数），或先硬币再金额（组合数）均可，因求最小值不影响结果
• 空间优化：可直接在原数组上操作，空间复杂度 O(amount)
• 提前终止：若硬币已排序，当 coin > i 时可提前结束内层循环

常见错误

• 错误初始化：未设置 dp[0]=0 或初始值过小
• 错误状态转移：误用 max 代替 min 或忽略硬币数量+1
• 遗漏边界：未处理硬币面额大于当前金额的情况
• 结果判断：直接返回 dp[amount] 而忘记检查是否有效

复杂度分析

• 时间复杂度：O(n×amount)，n 为硬币种类数
• 空间复杂度：O(amount)

扩展知识

• 变种问题：若求组合总数（LeetCode 518）需调整状态转移为 dp[i] += dp[i-coin]
• 贪心陷阱：硬币面额非倍数关系时（如 [3,5,7]），贪心算法可能失效
• BFS 解法：将问题转化为求从0到amount的最短路径，适合硬币面额较大时
• 记忆化搜索：自顶向下递归+缓存，避免计算不必要状态