# \[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\] 完全平方数](https://blessbingo.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/279-wan-quan-ping-fang-shu)很相似, 只是由于`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
```