第 57 课 - 零钱兑换

学习目标

理解问题本质：能够将“零钱兑换”问题抽象为动态规划问题。
掌握状态定义：学会定义 dp 数组，理解 dp[i] 的具体含义。
掌握状态转移：能够根据问题分析，推导出正确的状态转移方程。
分析复杂度：能够分析该解法的时间复杂度和空间复杂度，并与其他方法（如回溯、贪心）进行对比。
问题变体迁移：能够理解并解决该问题的常见变体（如组合总数）。

核心概念

想象你是一个收银员，需要用给定面值的硬币组合出特定的金额，并且要求使用的硬币数量最少。这就是 “零钱兑换”（Coin Change） 问题。

贪心算法为何失效？ 直觉上，我们可能会想：总是先用最大面值的硬币。但这常常得不到最优解。例如，硬币面值为 [1, 3, 4]，要凑出金额 6。

贪心策略：先用 4，剩下 2，再用两个 1，共 3 枚硬币 (4+1+1)。
最优解：使用两个 3，共 2 枚硬币 (3+3)。贪心策略忽略了硬币组合的灵活性，导致局部最优无法导向全局最优。

动态规划的思路：子问题的最优解 动态规划的核心思想是将原问题分解为相互重叠的子问题，并存储子问题的解以避免重复计算。对于金额 i，它的最少硬币数 dp[i] 可以由一个更小金额 j (j < i) 的最少硬币数 dp[j] 转移而来。具体来说，如果我们想凑出金额 i，我们可以选择使用一枚面值为 c 的硬币（前提是 c <= i），那么剩下的金额就是 i - c，其最少硬币数就是 dp[i - c]。所以，dp[i] = dp[i - c] + 1（这枚硬币 c）。

我们需要遍历所有可用的硬币面值 c，选择其中能使总硬币数最小的那个 c。

状态定义：dp[i] 表示凑出总金额 i 所需的最少硬币数量。 状态转移方程：dp[i] = min(dp[i], dp[i - coin] + 1)，其中 coin 是遍历每一个可用硬币面值。 初始化：dp[0] = 0（凑出金额 0 不需要硬币）。对于无法凑出的金额，我们将其初始化为一个不可能的极大值（如 float('inf')）。

代码示例

Python 实现

def coin_change(coins, amount):
    """
    计算凑出总金额所需的最少硬币个数
    :param coins: 硬币面值列表，如 [1, 2, 5]
    :param amount: 目标总金额
    :return: 最少硬币数，如果无法凑出则返回 -1
    """
    # 创建一个大小为 amount + 1 的 dp 数组，初始化为正无穷大
    # dp[i] 的含义是凑出金额 i 需要的最少硬币数
    dp = [float('inf')] * (amount + 1)
    
    # 基础情况：凑出金额 0 需要 0 个硬币
    dp[0] = 0
    
    # 遍历每一个需要计算的金额 i（从 1 到 amount）
    for i in range(1, amount + 1):
        # 对于当前金额 i，尝试使用每一枚硬币 coin
        for coin in coins:
            # 如果当前硬币面值 coin 小于等于当前金额 i
            if coin <= i:
                # 状态转移：尝试用当前硬币，看是否能得到更少的硬币数
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    # 如果 dp[amount] 仍然是正无穷大，说明无法凑出该金额
    return dp[amount] if dp[amount] != float('inf') else -1

# 测试代码
coins = [1, 2, 5]
amount = 11
result = coin_change(coins, amount)
print(f"硬币面值：{coins}，目标金额：{amount}")
print(f"最少需要的硬币数：{result}") # 输出应为 3 (5+5+1)

coins2 = [2]
amount2 = 3
result2 = coin_change(coins2, amount2)
print(f"\n硬币面值：{coins2}，目标金额：{amount2}")
print(f"最少需要的硬币数：{result2}") # 输出应为 -1 (无法凑出)

代码运行结果

硬币面值：[1, 2, 5]，目标金额：11
最少需要的硬币数：3

硬币面值：[2]，目标金额：3
最少需要的硬币数：-1

实践练习

练习 1：基础应用

给定硬币面值 [1, 5, 10, 25]，目标金额为 30。请手动模拟上述动态规划过程，填写前几个 dp 数组的值，并计算出最少需要多少枚硬币。

练习 2：问题变体 - 凑出总金额的组合数

“零钱兑换”还有一个姐妹问题：“零钱兑换 II”。它不再是求最少硬币数，而是求可以凑出总金额的硬币组合数（组合之间不考虑顺序，1+5 和 5+1 算同一种）。问题：请修改上面的代码，实现计算组合数的功能。

提示：
- 状态定义：dp[i] 表示凑出金额 i 的组合数。
- 初始化：dp[0] = 1 (凑出金额0有一种方案：什么都不选)。
- 遍历顺序：需要调整遍历顺序，先遍历硬币，再遍历金额，以避免重复计算排列。
预期输出：对于 coins = [1, 2, 5], amount = 5，应输出 4 种组合 ([5], [2,2,1], [2,1,1,1], [1,1,1,1,1])。

练习 3：综合应用 - 有限硬币

假设你手头的硬币数量是有限的。例如，你有 3 枚 1 元硬币和 2 枚 5 元硬币。现在要凑出 15 元，最少需要多少枚硬币？问题：设计一个算法来解决这个“有限硬币找零”问题。

提示：这可以看作是一个多重背包问题。状态定义可能需要增加一维来记录当前使用了哪些硬币，或者更高效的方法是使用状态压缩或优化后的多重背包解法。
预期：分析此问题与“无限硬币”问题的差异，并设计出解决方案的思路框架。

常见错误

滥用贪心算法：这是最典型的错误。必须理解贪心算法在本题中可能失效，动态规划才是通用解法。
初始化错误：
- 错误地将 dp[0] 初始化为 float('inf') 或其他非零值，这会导致状态转移方程出错。
- 忘记将无法凑出的金额（dp[amount]）对应地输出为 -1。
状态转移方程混淆：
- 误以为状态转移方程是 dp[i] = min(dp[i], dp[i-coin])（忘记加上当前这枚硬币）。
- 或者，在计算 dp[i-coin] 时，没有确保 i-coin >= 0，导致数组越界。在代码中通过 if coin <= i 条件避免。

小结

本节课我们学习了如何用动态规划解决经典的“零钱兑换”问题。

核心思想：将大问题（凑出金额 i）分解为小问题（凑出金额 i-coin），并利用子问题的最优解构建原问题的最优解。
关键步骤：
1. 定义状态：dp[i] 表示凑出金额 i 所需的最少硬币数。
2. 确定转移方程：dp[i] = min(dp[i], dp[i-coin] + 1)。
3. 初始化基础状态：dp[0] = 0。
4. 确定遍历顺序：通常是从 1 到 amount 依次计算。
复杂度分析：该解法的时间复杂度为 O(amount * len(coins))，空间复杂度为 O(amount)。
思维拓展：该问题是 完全背包问题 的一个特例（每种物品/硬币可以无限次取用）。掌握了它的思想，可以帮助你理解更广泛的背包问题。

理解动态规划解决问题的“状态定义”和“状态转移”是精髓，多加练习，你就能举一反三。

练习编辑器

rust