LeetCode 第322题：零钱兑换

📖 文章摘要

本文详细解析LeetCode第322题“零钱兑换”，这是一道经典的动态规划问题。文章提供了动态规划和贪心+DFS两种解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升动态规划能力的程序员。

核心知识点： 动态规划、贪心算法、深度优先搜索
难度等级： 中等
推荐人群： 具有基础算法知识，想要提升动态规划能力的程序员

题目描述

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

解题思路

方法一：动态规划

使用动态规划自底向上求解，定义dp[i]表示凑成金额i所需的最少硬币数。

关键点：

状态定义：dp[i]表示凑成金额i所需的最少硬币数
状态转移：dp[i] = min(dp[i], dp[i - coin] + 1)
初始化：dp[0] = 0，其他位置初始化为无穷大
遍历顺序：外层遍历金额，内层遍历硬币

具体步骤：

创建dp数组，初始化为无穷大
设置dp[0] = 0
遍历每个金额i
对每个金额，遍历每个硬币面额
更新dp[i]的最小值

时间复杂度：O(amount * coins.length) 空间复杂度：O(amount)

方法二：贪心 + DFS

使用贪心思想优先选择大面额硬币，通过DFS搜索所有可能的组合。

关键点：

将硬币数组降序排序
优先尝试大面额硬币
当前选择无法得到结果时回溯
使用计数变量记录当前使用的硬币数

具体步骤：

对硬币数组降序排序
从大到小尝试每个面额的硬币
当无法继续使用当前面额时，回溯到上一个面额
记录过程中的最小硬币数

时间复杂度：O(S^n)，其中S是金额，n是硬币数量空间复杂度：O(n)

图解思路

动态规划状态转移表

金额i	dp[i]初始值	可选硬币	更新后的dp[i]	选择的硬币
0	0	-	0	-
1	∞	[1]	1	1
2	∞	[1,2]	1	2
3	∞	[1,2]	2	2+1
4	∞	[1,2]	2	2+2
5	∞	[1,2,5]	1	5

DFS搜索过程表

当前金额	已用硬币数	选择硬币	剩余金额	是否可行
11	0	5	6	是
6	1	5	1	是
1	2	1	0	是

代码实现

C# 实现

public class Solution {
    public int CoinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Array.Fill(dp, amount + 1);
        dp[0] = 0;
        
        for (int i = 1; i <= amount; i++) {
            foreach (int coin in coins) {
                if (coin <= i) {
                    dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

Python 实现

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (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] != float('inf') else -1

C++ 实现

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

执行结果

C# 实现

执行用时：92 ms
内存消耗：38.2 MB

Python 实现

执行用时：1124 ms
内存消耗：15.7 MB

C++ 实现

执行用时：48 ms
内存消耗：14.5 MB

性能对比

语言	执行用时	内存消耗	特点
C#	92 ms	38.2 MB	实现简洁，性能适中
Python	1124 ms	15.7 MB	代码最简洁，但性能较差
C++	48 ms	14.5 MB	性能最优

代码亮点

🎯 使用动态规划高效求解
💡 巧妙设置初始值避免特判
🔍 通过比较dp[amount]判断是否有解
🎨 代码简洁优雅，易于理解

常见错误分析

🚫 初始化dp数组时使用错误的值
🚫 没有考虑硬币金额大于目标金额的情况
🚫 遍历顺序错误导致结果不正确
🚫 返回值的判断条件设置不当

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
动态规划	O(amount * n)	O(amount)	效率高，结果准确	空间消耗较大
贪心+DFS	O(S^n)	O(n)	空间消耗小	时间复杂度高

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第322题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

示例 3：

提示

解题思路

方法一：动态规划

方法二：贪心 + DFS

图解思路

动态规划状态转移表

DFS搜索过程表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流