LeetCode 热题 100 322. 零钱兑换

LeetCode 热题 100 | 322. 零钱兑换

大家好，今天我们来解决一道经典的动态规划问题——零钱兑换。这道题在 LeetCode 上被标记为中等难度，要求找到凑成给定总金额所需的最少硬币个数。

---

问题描述

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

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

---

解题思路

核心思想

1. 动态规划：

   • 使用动态规划（DP）来解决这个问题。
   • 定义 dp[i] 为凑成总金额 i 所需的最少硬币个数。
   • 状态转移方程为：
     [
     dp[i] = \min_{c \in coins} (dp[i - c] + 1)
     ]
     其中，c 是硬币的面额，且 c <= i。

2. 初始化：

   • dp[0] = 0，因为凑成总金额 0 所需的硬币个数是 0。

3. 遍历：

   • 从 1 到 amount 遍历，对于每个 i，找到所有小于等于 i 的硬币面额 c，并更新 dp[i]。

---

状态转移方程的推导

1. 定义状态

dp[i] 表示凑成总金额 i 所需的最少硬币个数。

2. 状态转移

假设我们已经知道了所有小于 i 的 dp 值，现在需要计算 dp[i]。为了得到凑成总金额 i 所需的最少硬币个数，我们可以尝试以下方法：

• 选择一个硬币：选择一个硬币面额 c，使得 c <= i。
• 计算剩余金额：如果选择了硬币面额 c，那么剩下的金额就是 i - c。
• 递归关系：因此，dp[i] 可以表示为 dp[i - c] + 1，其中 +1 表示我们选择了一个硬币面额 c。

3. 选择最优解

由于硬币面额 c 有多种可能（例如 [1, 2, 5]），我们需要在所有可能的硬币面额中选择一个使得 dp[i - c] + 1 最小的值。因此，状态转移方程为：

[
dp[i] = \min_{c \in coins} (dp[i - c] + 1)
]

详细解释

假设我们正在计算 dp[11]，即凑成总金额 11 所需的最少硬币个数。我们可以尝试以下硬币面额：

• 选择 c = 1：

  • 剩下的金额是 11 - 1 = 10。
  • 因此，dp[11] = dp[10] + 1。

• 选择 c = 2：

  • 剩下的金额是 11 - 2 = 9。
  • 因此，dp[11] = dp[9] + 1。

• 选择 c = 5：

  • 剩下的金额是 11 - 5 = 6。
  • 因此，dp[11] = dp[6] + 1。

我们需要在这些选择中找到最小值：

[
dp[11] = \min(dp[10] + 1, dp[9] + 1, dp[6] + 1)
]

Python代码实现

class Solution:def coinChange(self, coins, amount):""":type coins: List[int]:type amount: int:rtype: int"""dp = [float('inf')] * (amount + 1)dp[0] = 0for i in range(1, amount + 1):for c in coins:if i - c >= 0:dp[i] = min(dp[i], dp[i - c] + 1)return dp[amount] if dp[amount] != float('inf') else -1

代码解析

1. 初始化：

   • dp 数组初始化为长度为 amount + 1 的列表，所有值初始化为无穷大（float('inf')），表示初始状态下的最少硬币个数是无穷大。
   • dp[0] = 0，因为凑成总金额 0 所需的硬币个数是 0。

2. 状态转移：

   • 遍历从 1 到 amount 的每个整数 i。
   • 对于每个 i，遍历所有硬币面额 c。
   • 如果 i - c >= 0，则更新 dp[i] 为 dp[i - c] + 1 的最小值。

3. 返回结果：

   • 最终结果存储在 dp[amount] 中。
   • 如果 dp[amount] 仍然是 float('inf')，则表示无法凑成总金额，返回 -1。

---

复杂度分析

• 时间复杂度：O(n * m)，其中 n 是总金额 amount，m 是硬币种类数 len(coins)。对于每个 i，需要遍历所有硬币面额。
• 空间复杂度：O(n)，使用了长度为 amount + 1 的 dp 数组。

---

示例运行

示例 1

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

示例 2

输入：coins = [2], amount = 3
输出：-1

示例 3

输入：coins = [1], amount = 0
输出：0

---

总结

通过动态规划的方法，我们可以高效地解决零钱兑换问题。状态转移方程 dp[i] = \min_{c \in coins} (dp[i - c] + 1) 确保了我们能够找到凑成总金额所需的最少硬币个数。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

关注我，获取更多算法题解和编程技巧！