动态规划题解_零钱兑换【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

方法一：递归 + 记忆化搜索（DFS + cache）

一、算法逻辑（逐步思路）

❓ 题目目标：

给定一个 coins 数组（硬币面值）和一个目标金额 amount，
要求用最少的硬币数凑出 amount，凑不出来就返回 -1。

✅ 思路解析（使用 DFS + 记忆化）：

1. 使用递归函数 dfs(i, c)：

• 表示：只使用前 i 个硬币（coins[0] 到 coins[i]），凑出金额 c 所需的最小硬币数。

2. 基本边界情况：

• 如果 i < 0，即没有任何硬币可用了：

• • 如果金额 c == 0，刚好凑出，返回 0；
  • 否则说明无法凑出，返回 inf 表示不合法解。

3. 决策逻辑：

• 如果当前硬币 coins[i] 比当前金额 c 还大：不能选它，只能尝试不选：dfs(i - 1, c)；
• 否则有两种选择：

• • 不选当前硬币：dfs(i - 1, c)；
  • 继续选当前硬币（不限次数）：dfs(i, c - coins[i]) + 1；
  • 二者取较小值作为当前子问题的解。

4. 返回最终解：

• 初始从 dfs(len(coins) - 1, amount) 开始；
• 若结果为无穷大（表示无解），则返回 -1；否则返回结果。

5. 使用 @cache 实现记忆化搜索，避免重复递归，提高性能。

二、算法核心点

✅ 核心思想：完全背包问题的 DFS + 记忆化版本

• 本质是“无限背包问题”：每个硬币可以用无数次；
• 每个子问题有两个选择：选 / 不选当前硬币；
• 利用 DFS 递归地表示子问题，再用缓存装饰器 @cache 减少重复子问题计算；
• 与普通 DP 不同的是，这里使用了自顶向下的搜索方式（递归）而非自底向上的表格填充。

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）def dfs(i: int, c: int) -> int:if i < 0:return 0 if c == 0 else infif c < coins[i]:  # 只能不选return dfs(i - 1, c)# 不选 vs 继续选return min(dfs(i - 1, c), dfs(i, c - coins[i]) + 1)ans = dfs(len(coins) - 1, amount)return ans if ans < inf else -1

三、复杂度分析

• 时间复杂度：O(n × amount)

• • 有 n 个硬币，最多可能对每个金额（0~amount）都调用一次；
  • 利用缓存后，每个状态 dfs(i, c) 最多被计算一次。

• 空间复杂度：O(n × amount)

• • 缓存占用的空间，与状态数量一致；
  • 另外递归栈深度最大为 O(amount)，在极端情况下。

总结表：

方法二：1:1 翻译成递推后，进行空间优化：两个数组（滚动数组）

一、算法逻辑（逐步思路）

❓ 问题目标：

给定一个整数数组 coins（代表硬币的面额）和一个整数 amount，求凑成 amount 最少需要多少枚硬币，如果无法凑成返回 -1。

✅ 思路解析（完全背包问题）

1. 定义状态：

• • f[i][c] 表示使用前 i 个硬币（从 coins[0] 到 coins[i-1]）凑成金额 c 所需的最少硬币数。
  • 初始化为 inf 表示初始时不可达；
  • 特别地，f[0][0] = 0 表示用 0 个硬币凑出金额 0，需要 0 枚硬币。

1. 状态转移：
   对于每种硬币 x = coins[i] 和金额 c，有两种选择：

• • 不选第 i 个硬币：f[i+1][c] = f[i][c]；
  • 选第 i 个硬币：f[i+1][c] = f[i+1][c - x] + 1（可以多次选，注意状态沿着 i+1 更新）

1. 使用滚动数组优化：

• • 因为 f[i+1][...] 只依赖于 f[i][...] 和 f[i+1][...]，所以只需要 2 行数组就能完成转移；
  • f[i % 2] 表示上一轮，f[(i + 1) % 2] 表示当前轮；
  • 每次处理完第 i 个硬币后，数组换一次行，节省空间。

1. 返回最终解：

• • 答案是 f[n % 2][amount]（n 是硬币数量）；
  • 如果这个值仍为 inf，说明无解，返回 -1。

二、算法核心点

✅ 核心思想：完全背包的二维动态规划 + 空间优化

• 本质是完全背包问题（每个物品可以选多次）；
• 将状态定义为“前 i 个硬币构成 c 的最小硬币数”；
• 使用滚动数组优化空间，把 O(n × amount) 降为 O(2 × amount)。

这种写法特别适合面试时展示「从朴素二维 DP 优化到空间压缩」的过程。

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:n = len(coins)f = [[inf] * (amount + 1) for _ in range(2)]f[0][0] = 0for i, x in enumerate(coins):for c in range(amount + 1):if c < x:f[(i + 1) % 2][c] = f[i % 2][c]else:f[(i + 1) % 2][c] = min(f[i % 2][c], f[(i + 1) % 2][c - x] + 1)ans = f[n % 2][amount]return ans if ans < inf else -1

三、复杂度分析

• 时间复杂度：O(n × amount)

• • 外层循环 n 次（硬币种数），内层循环最多 amount+1 次。

• 空间复杂度：O(2 × amount) = O(amount)

• • 使用滚动数组，只保留两行状态，节省空间。

总结表：