# \[322]\[中等]\[动态规划]\[背包]\[DFS] 零钱兑换

## 题目描述

[322. 零钱兑换](https://leetcode-cn.com/problems/coin-change/)

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

```
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
```

示例 2:

```
输入: coins = [2], amount = 3
输出: -1
```

说明:

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

## 解题思路

### 动态规划

与[\[279\]\[中等\]\[动态规划\]\[背包\]\[BFS\] 完全平方数](/garnet/suan-fa/dong-tai-gui-hua/279-wan-quan-ping-fang-shu.md)很相似, 只是由于`1`可能不存在, 因最终可能没有答案. 按照每次考虑添加一个硬币, 从0逐渐推算到总金额. 考虑状态`dp[i][v]`表示使用前`i`种硬币, 构成总金额为`v`的最少硬币数量. 我们使用`inf`代表没有组合方案, 以方便比较最小值, 简化状态转移方程, 在最后输出答案的时候, 按题目要求转换成-1即可.

**滚动数组**优化空间复杂度的版本.

```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0

        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)
        return dp[-1] if dp[-1] != float('inf') else -1
```

或者这样考虑, 对于总金额`v`, 遍历所有硬币情况, 去掉这个硬币, 取其中的最小值. 当去掉某个硬币后总金额小于0, 说明方案不可行, 使用`inf`表示.

```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0

        for i in range(1, amount + 1):
            for coin in coins:
                dp[i] = min(dp[i], (dp[i - coin] if i - coin >= 0 else float('inf')) + 1)
        return dp[-1] if dp[-1] != float('inf') else -1
```

### DFS

使用动态规划的思路, 其实是**自下而上**, 即从0逐渐推算到最后的总金额`n`. 我们也可以转化成**自上而下**的思路, 这就是DFS的思路. 再使用LRU缓存中间结果, 防止重复计算.

```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        @lru_cache(None)
        def dfs(number):
            if number == 0:
                return 0
            if number < 0:
                return float('inf')

            min_count = float('inf')
            for coin in coins:
                min_count = min(min_count, dfs(number - coin) + 1)
            return min_count

        ans = dfs(amount)
        return ans if ans != float('inf') else -1
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blessbingo.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/322-ling-qian-dui-huan.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.