# \[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/garnetow/garnetbook/tree/bc3997b8da19691b7ab43aec6c322306eae28330/Algorithm/动态规划/Algorithm/动态规划/08.11-硬币.md). 注意区别是由于可能没有面值为1的硬币, 某总金额可能出现无法组合的情况, 使用`inf`标记. 在进行状态转移的时候要注意区分这种情况.

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

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

        for i in range(len(coins)):
            coin = coins[i]
            for j in range(coin, amount + 1):
                dp[j] = dp[j] + dp[j - coin]
        return dp[-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://kerasnoone.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/518-ling-qian-dui-huan-ii.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.