50 | 面试题：零钱兑换-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

50 | 面试题：零钱兑换

在算法面试中，零钱兑换（Coin Change）是一个经典而富有挑战性的动态规划问题，它不仅考验了面试者对动态规划思想的理解深度，还要求在有限的时间内设计出高效、准确的解决方案。本讲将深入剖析零钱兑换问题的本质，提供多种解题思路，并重点讲解动态规划方法的应用，最后通过代码实现加深理解。

一、问题描述

给定一个目标金额n（整数）和一个硬币种类列表coins（整数数组，每种硬币的面值），你需要计算并返回凑成目标金额所需的最少硬币个数。如果无法凑成目标金额，则返回-1。

二、问题分析

暴力解法：最直接的方法是尝试所有可能的硬币组合，但这种方法的时间复杂度会随着目标金额和硬币种类的增加而呈指数级增长，对于稍大的输入将变得不可行。
贪心算法：虽然直觉上可能会想到按硬币面值从大到小（或从小到大）的顺序尝试使用硬币，但这种方法并不能保证得到最少硬币个数的解。例如，对于coins = [1, 5, 10]和n = 15，贪心算法可能会先选择10，再选5，最后选两个1，共8个硬币，而最优解是三个5。
动态规划：鉴于上述方法的局限性，动态规划成为解决零钱兑换问题的最佳选择。动态规划通过保存子问题的解来避免重复计算，从而显著降低时间复杂度。

三、动态规划解法

1. 定义状态

设dp[i]表示凑成金额i所需的最少硬币个数。注意，这里的i从0开始，即dp[0] = 0，表示凑成金额为0不需要任何硬币。

2. 状态转移方程

对于任意金额i（i > 0），我们可以通过遍历硬币种类列表coins，尝试从每种硬币开始凑成金额i。如果当前硬币的面值为coin，且i - coin是一个有效的、已经计算过的金额，则我们可以将dp[i]更新为dp[i - coin] + 1（即使用当前硬币后，剩余金额所需的最少硬币数加1）和之前dp[i]的较小值。如果所有硬币都无法用于凑成金额i，则dp[i]应保持为一个较大的值（如初始化为n+1），表示无法凑成。

状态转移方程可表示为：

[
dp[i] = \min_{coin \in coins} (dp[i - coin] + 1) \quad \text{if } i - coin \geq 0 \text{ 且 } dp[i-coin] \neq \text{初始大值}
]

如果所有dp[i-coin]都是初始大值，则dp[i]也应保持为初始大值。

3. 初始化

dp[0] = 0，表示凑成金额为0不需要任何硬币。
对于其他dp[i]（i > 0），初始化为一个较大的值（如n+1），表示当前还无法凑成该金额。

4. 遍历顺序

由于每个dp[i]的值依赖于比它小的dp[j]（j < i），因此我们需要从dp[1]开始，逐步计算到dp[n]。

5. 结果判断

最后，如果dp[n]仍然是初始大值，则表示无法凑成目标金额，返回-1；否则，返回dp[n]作为最少硬币个数。

四、代码实现

def coinChange(coins: List[int], amount: int) -> int:
    # 初始化dp数组
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    # 动态规划计算
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin and dp[i - coin] != float('inf'):
                dp[i] = min(dp[i], dp[i - coin] + 1)
    # 判断是否可以凑成目标金额
    return dp[amount] if dp[amount] != float('inf') else -1
# 示例
coins = [1, 2, 5]
amount = 11
print(coinChange(coins, amount))  # 输出: 3

五、优化思考

虽然上述动态规划解法已经相当高效，但在某些极端情况下（如硬币种类极多但金额较小），我们可能还可以进一步优化。例如，通过预处理某些信息来减少不必要的计算，或者采用更高级的数据结构（如线段树、树状数组等）来优化查询效率。然而，这些优化通常基于特定场景，且实现复杂度较高，需要根据实际问题灵活选择。

六、总结

零钱兑换问题是一个典型的动态规划应用实例，通过定义状态、构建状态转移方程、合理初始化以及正确的遍历顺序，我们可以高效地解决这类问题。在面试中，熟练掌握这类问题的解法不仅能展现你的算法能力，还能体现你对动态规划思想的深刻理解。希望本讲的内容能对你有所帮助，祝你在算法面试中取得优异成绩！