> For the complete documentation index, see [llms.txt](https://blessbingo.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blessbingo.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/518-ling-qian-dui-huan-ii.md).

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

## 题目描述

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

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:

```
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
```

示例 2:

```
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
```

示例 3:

```
输入: amount = 10, coins = [10]
输出: 1
```

注意:

你可以假设：

* 0 <= amount (总金额) <= 5000
* 1 <= coin (硬币面额) <= 5000
* 硬币种类不超过 500 种
* 结果符合 32 位符号整数

## 解题思路

思路参考[\[面试题 08.11\]\[中等\]\[动态规划\]\[背包\] 硬币](https://github.com/databinQ/garnetbook/tree/ab5317a3be967f962993dc7f634ab856fdba6420/Algorithm/动态规划/Algorithm/动态规划/08.11-硬币.md). 注意区别是由于可能没有面值为1的硬币, 某总金额可能出现无法组合的情况, 使用`inf`标记. 在进行状态转移的时候要注意区分这种情况.

下面的方法使用了**滚动数组**.

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

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