硬币找零问题是一个经典的动态规划问题,给定一系列不同面值的硬币和一个总金额,计算出选取最少的硬币数量,使得这些硬币面值之和等于给定的总金额。
硬币找零问题是动态规划的经典应用场景之一,核心思想是求解如何用给定面值的硬币组合出指定金额,并且使用的硬币数量最少。这个问题在计算机科学与数学领域都有广泛应用,是理解动态规划思想的绝佳例子。
硬币找零问题可以通过动态规划高效求解,时间复杂度为O(n×m),其中n是目标金额,m是硬币面值的种类数。该问题体现了最优子结构与重叠子问题这两个动态规划的关键特性。
给定不同面值的硬币(无限量)和一个总金额,问能凑成总金额的最少硬币个数是多少。例如,硬币面值为[1, 2, 5],总金额为11时,最少需要3个硬币(5+5+1=11)。如果不能凑出该金额,则返回-1。
硬币找零问题是完全背包问题的一种特例,每种硬币可以重复使用多次。
以一个具体的硬币找零问题为例,详细说明动态规划的过程:
...