好的，我们来看 LeetCode 第 322 题「零钱兑换」。

题目描述

给你一个整数数组 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

解题思路：动态规划

这个问题是经典的“完全背包”类问题，适合用动态规划解决。核心思想是：要凑出金额 i，我们可以从 coins 里选一枚硬币 coin，然后问题转化为凑出金额 i - coin 的最少硬币数，再加 1（代表选的这枚硬币）。

步骤 1：定义状态

我们定义一个数组 dp，其中：

• dp[i] 表示凑出金额 i 所需的最少硬币个数。
• 我们的目标是求 dp[amount]。

步骤 2：初始化

• dp[0] = 0：凑出金额 0 需要 0 枚硬币。
• 对于其他 i 从 1 到 amount，我们初始设 dp[i] = amount + 1（或一个很大的数，比如 float('inf')），表示暂时无法凑出。因为最多用 amount 枚 1 元硬币，所以 amount + 1 相当于无穷大。

步骤 3：状态转移方程

对于每个金额 i 从 1 到 amount，遍历每个硬币 coin：

• 如果 coin <= i（表示这枚硬币可以用于凑金额 i），那么：

\[ dp[i] = \min(dp[i], dp[i - coin] + 1) \]

意思是：看看用这枚硬币的情况下，是否比已知方案更优。

步骤 4：填表计算

我们从小到大计算 dp[1] 到 dp[amount]，确保在计算 dp[i] 时，dp[i - coin] 已经计算过。

步骤 5：返回结果

如果 dp[amount] > amount，说明无法凑出，返回 -1；否则返回 dp[amount]。

举例说明

以 coins = [1, 2, 5], amount = 11 为例：

1. 初始化 dp = [0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]（长度 12，索引 0~11）。

2. 计算过程：

   • i = 1：硬币 1 可用，dp[1] = min(12, dp[0] + 1) = 1
   • i = 2：硬币 1 可用 → dp[2] = min(12, dp[1] + 1) = 2；硬币 2 可用 → dp[2] = min(2, dp[0] + 1) = 1
   • i = 3：硬币 1 可用 → dp[3] = min(12, dp[2] + 1) = 2；硬币 2 可用 → dp[3] = min(2, dp[1] + 1) = 2
   • i = 4：硬币 1 可用 → dp[4] = min(12, dp[3] + 1) = 3；硬币 2 可用 → dp[4] = min(3, dp[2] + 1) = 2
   • i = 5：硬币 1 可用 → dp[5] = min(12, dp[4] + 1) = 3；硬币 2 可用 → dp[5] = min(3, dp[3] + 1) = 3；硬币 5 可用 → dp[5] = min(3, dp[0] + 1) = 1
   • 继续计算到 i = 11：
     • 最终 dp[11] 会由 dp[10] + 1（硬币 1）、dp[9] + 1（硬币 2）、dp[6] + 1（硬币 5）等比较得出最小值 3。

3. 结果：dp[11] = 3。

代码实现（Python）

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

复杂度分析

• 时间复杂度：O(amount × len(coins))
• 空间复杂度：O(amount)

这样，我们就用动态规划解决了“零钱兑换”问题。它的关键点是定义好状态、初始化、状态转移，并从小到大填表。