322. 零钱兑换

题目链接：322. 零钱兑换

题目描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

核心思考：完全背包思想（DFS + 记忆化）

与“完全平方数”问题类似，这道题是完全背包问题的最典型应用。我们要寻找用无限数量的可选面额凑出目标值的最小件数。

1. 状态定义：设 dfs(i, c) 表示使用前 i 种面额的硬币，凑出金额 c 所需的最少硬币个数。
2. 转移方程：
   • 如果凑不进（c < coins[i]）：当前硬币面额太大，直接考虑前一种：dfs(i - 1, c)。
   • 如果凑得进：我们可以选择不选这种硬币 dfs(i - 1, c)，或者选一个这种硬币后继续在同一层挑选 dfs(i, c - coins[i]) + 1。二者取最小值。
3. 递归边界：
   • 当 i < 0 时，已经没有可选硬币。如果此时目标 c == 0，返回 0；否则说明凑不齐，返回无穷大 inf。
4. 性能保障：使用 @cache 装饰器进行记忆化搜索。状态的数量级为硬币种类数乘以金额，通过空间换时间避免冗余递归。
5. 最终判分：如果递归返回结果为 inf，则返回 -1。

解题思路 (Python)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        
        # 递归定义：用前 i 种硬币凑出金额 c 所需的最少硬币个数
        @cache
        def dfs(i, c):
            # 边界：已遍历完所有面额
            if i < 0:
                return 0 if c == 0 else inf
            
            # 如果剩余金额小于当前面额，必须跳过
            if c < coins[i]:
                return dfs(i - 1, c)
            
            # 决策：min(不使用当前面额, 使用一枚当前面额后继续在当前索引尝试)
            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 \times C)$，其中 $N$ 是硬币种类数，$C$ 是目标金额 amount。总状态数为 $N \times C$，每个状态计算复杂度为 $O(1)$。
• 空间复杂度：$O(N \times C)$。用于缓存每个状态的结果。