【内部资料】给定一组硬币的面额和一个总金额，编写一个程序来找零钱，使得所需的硬币数量最少。假设你拥有足够数量的每种硬币。既可以用贪心法又可以用动态规划，到底用哪个好呢？还是都好，他们的区别又在哪里呢
给定一组硬币的面额和一个总金额，编写一个程序来找零钱，使得所需的硬币数量最少。假设你拥有足够数量的每种硬币。既可以用贪心法又可以用动态规划，到底用哪个好呢？还是都好，他们的区别又在哪里呢？
对于这个问题，既可以使用贪心法也可以使用动态规划来解决，但它们在某些方面有明显的区别：
贪心法：
贪心法可以是一个有效的解决方法，特别是当硬币的面额是常见的分值（如1、5、10、25美分等）时。
贪心法每次选择最大面额的硬币，以尽量减小剩余的总金额，从而减少所需的硬币数量。这在某些情况下可以得到很好的结果，尤其是当硬币面额之间有较大的公约数时。
然而，贪心法不一定对所有硬币面额都适用，因为一些特殊的硬币组合可能需要动态规划才能找到最优解。
动态规划：
动态规划是一种更通用的方法，适用于各种硬币面额的情况，并且可以提供确切的最优解。
动态规划通过将问题拆分为子问题，并记录每个子问题的最优解，然后组合这些子问题的解决方案来找到全局最优解。
动态规划对于复杂的问题和硬币面额之间没有明显公约数的情况非常有用。它可以处理更一般的情况，无需依赖硬币面额的特殊性质。
关键区别：
贪心法是一种简单且直观的方法，适用于特定情况，通常更容易实现和理解。它可能提供近似最优解，但不一定能保证全局最优解。
动态规划是一种更强大的方法，适用于各种情况，可以提供确切的最优解。它通常需要更多的计算资源和内存，因为它涉及到子问题的存储和计算。
总的来说，对于找零钱问题，如果硬币面额比较特殊且有贪心选择性质，贪心法可能足够。但如果需要确切的最优解或面额较为一般，动态规划可能更适合。最终的选择取决于问题的性质、精确性要求和问题规模。
让我提供一个更具体的例子来说明为什么硬币面额之间有较大的公约数时贪心法更容易获得最优解：
假设有两种硬币面额：6元和9元，需要找零15元。在这种情况下，硬币面额之间的最大公约数是3。如果我们使用贪心法，它会按照如下方式选择硬币：
先选择9元硬币，剩余需要找零6元。
接着选择6元硬币，完成找零。
贪心法的选择策略是正确的，它找到了最优解，使用的硬币数量最少，因为硬币面额之间的最大公约数有助于找到全局最优解。这个例子说明了在某些情况下，贪心法可以得到最优解，尤其是当硬币面额之间有较大的公约数时。
如果硬币面额之间没有较大的公约数，例如硬币面额是3元和7元，需要找零8元，那么贪心法可能无法得到最优解。在这种情况下，贪心法可能会选择两个3元硬币，但最优解是选择一个7元硬币和一个1元硬币。
因此，贪心法在硬币面额之间有较大的公约数时更容易获得最优解，因为硬币的组合能够累积到全局最优解。然而，贪心法并不是所有问题的最佳解决方法，问题的性质和硬币面额的选择都会影响到贪心法的适用性。
