硬币找零问题

算法

硬币找零问题是一个经典的动态规划问题,给定一系列不同面值的硬币和一个总金额,计算出选取最少的硬币数量,使得这些硬币面值之和等于给定的总金额。

时间复杂度:最佳 O(n×m) | 平均 O(n×m) | 最差 O(n×m)
空间复杂度:O(n)

应用场景/前提条件

  • 动态规划
  • 贪心算法
  • 最优子结构

算法讲解

硬币找零问题

介绍

硬币找零问题是动态规划的经典应用场景之一,核心思想是求解如何用给定面值的硬币组合出指定金额,并且使用的硬币数量最少。这个问题在计算机科学与数学领域都有广泛应用,是理解动态规划思想的绝佳例子。

硬币找零问题可以通过动态规划高效求解,时间复杂度为O(n×m),其中n是目标金额,m是硬币面值的种类数。该问题体现了最优子结构与重叠子问题这两个动态规划的关键特性。

问题定义

给定不同面值的硬币(无限量)和一个总金额,问能凑成总金额的最少硬币个数是多少。例如,硬币面值为[1, 2, 5],总金额为11时,最少需要3个硬币(5+5+1=11)。如果不能凑出该金额,则返回-1。

硬币找零问题是完全背包问题的一种特例,每种硬币可以重复使用多次。

算法步骤

  1. 定义状态:dp[i]表示组成金额i所需的最少硬币数量
  2. 确定边界条件:dp[0] = 0,表示组成金额0需要0个硬币
  3. 状态转移方程:dp[i] = min(dp[i], dp[i-coin] + 1),其中coin为某个硬币面值
  4. 遍历所有可能的金额与硬币组合
  5. 最终答案为dp[amount](amount 是总金额),如果为无穷大则表示无法组成该金额

算法详解

以一个具体的硬币找零问题为例,详细说明动态规划的过程:

...