LeetCode 322. 零钱兑换 题目描述 给定不同面额的硬币 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 解题过程循序渐进讲解 第一步：理解问题与暴力思路 我们需要用最少数量的硬币凑出 amount 。由于每种硬币无限使用，这是一个“完全背包”类的最小化问题。 最直接的思路是“搜索”：对于当前金额 a ，尝试每一种硬币 coin ，然后递归求解子问题 a - coin 的最小硬币数，最后取最小值加 1。但这样会重复计算很多子问题，时间复杂度是指数级的。 第二步：定义动态规划状态 定义 dp[i] 为凑出金额 i 所需的最少硬币个数。 目标是求 dp[amount] 。 初始状态： dp[0] = 0 （金额 0 不需要硬币）。 其他金额初始化为一个很大的数（比如 amount + 1 或 INT_MAX ），表示暂时不可达。 第三步：状态转移方程 对于每个金额 i 从 1 到 amount ，我们尝试每一种硬币 coin （如果 coin <= i ）： dp[i] = min(dp[i], dp[i - coin] + 1) 含义是：如果使用这枚 coin ，那么凑出 i 的最小数量等于凑出 i - coin 的最小数量再加 1（这枚硬币）。我们取所有可能硬币中的最小值。 第四步：计算顺序 由于 dp[i] 依赖于 dp[i - coin] （ i - coin 小于 i ），所以按金额从小到大计算即可。 对于每个 i ，遍历所有硬币尝试更新。 第五步：边界与最终结果 如果 dp[amount] 仍然是初始的大数值，说明无法凑出，返回 -1 ；否则返回 dp[amount] 。 注意金额 0 的情况直接返回 0。 第六步：举例说明 以 coins = [1, 2, 5] , amount = 11 为例： 初始化 dp = [0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12] （ dp[0]=0 ，其他为 12，因为最大硬币数不会超过 11 枚） i=1 ：硬币 1 可用， dp[1] = min(12, dp[0]+1) = 1 i=2 ：硬币 1 得 dp[2] = dp[1]+1 = 2 ；硬币 2 得 dp[0]+1 = 1 ，取最小 1 i=3 ：硬币 1 得 dp[2]+1 = 2 ；硬币 2 得 dp[1]+1 = 2 ，取 2 继续计算到 i=11 ： 用硬币 1： dp[10]+1 = 2+1=3 （因为 dp[ 10 ]=2，由两枚 5 组成） 用硬币 2： dp[9]+1 = 3+1=4 用硬币 5： dp[6]+1 = 2+1=3 （dp[ 6 ]=2，由 5+1 或 2+2+2 等得到） 最终 dp[11] = 3 第七步：复杂度分析 时间复杂度：O(amount * n)，其中 n 是硬币种类数。 空间复杂度：O(amount)，用于 dp 数组。 第八步：关键点 初始化 dp[0] = 0 ，其他为较大值。 遍历金额时，内层遍历所有硬币尝试更新。 如果最终值未更新，返回 -1。 这是动态规划的完全背包最小值问题，与搜索、BFS 也可解，但 DP 更直接清晰。