LeetCode 沉思：硬币找零

在算法学习的道路上，LeetCode 里的硬币找零问题是一个经典且富有挑战性的题目。它不仅考验我们对算法逻辑的理解，更促使我们思考如何高效地解决实际生活中的组合优化问题。

硬币找零问题通常表述为：给定不同面额的硬币和一个总金额，计算凑出这个总金额所需的最少硬币数量。例如，有面额为 1 元、5 角、1 角的硬币，要凑出 1 元 3 角，怎样组合硬币能使数量最少呢？

解决这类问题，贪心算法是首先会被想到的思路。贪心算法的核心是在每一步选择中都采取当前状态下的最优决策。在硬币找零中，就是每次都优先选择面额最大的硬币。在上述例子里，我们会先选 1 枚 1 元硬币，然后再选 3 枚 1 角硬币，总共 4 枚硬币。然而，贪心算法并非在所有情况下都能得到最优解。比如，若硬币面额为 1 元、7 角、1 角，要凑出 1 元 4 角，按照贪心算法，会先选 1 枚 1 元硬币，剩下 4 角则需要 4 枚 1 角硬币，总共 5 枚硬币。但实际上，选择 2 枚 7 角硬币才是最优解，只需要 2 枚硬币。

动态规划算法成为解决硬币找零问题的更可靠方法。动态规划的关键在于将大问题分解为多个子问题，并通过保存子问题的解来避免重复计算。我们可以创建一个数组，数组的索引表示金额，数组的值表示凑出该金额所需的最少硬币数量。从金额 0 开始，逐步计算到目标金额。每计算一个金额，都遍历所有面额的硬币，看使用当前硬币能否得到更少的硬币数量。

通过对硬币找零问题的深入思考，我们不仅掌握了不同算法在实际问题中的应用，还锻炼了逻辑思维和问题解决能力。在面对复杂的算法挑战时，我们需要不断尝试不同的方法，深入理解每种算法的优缺点，从而找到最适合的解决方案。这也正是 LeetCode 题目带给我们的宝贵收获，帮助我们在算法领域不断进步。