# 518. 零钱兑换 II

<https://leetcode-cn.com/problems/coin-change-2/>

## 解法一：暴力dfs递归（超时）

为防止重复，dfs函数设一个start，每次从start向后循环（不回头）

```python
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        self.res = 0
        self.dfs(amount, coins, 0, 0)
        return self.res
    
    def dfs(self, amount, coins, sum, start):
        if sum > amount:
            return
        elif sum == amount:
            self.res += 1
        for i in range(start, len(coins)):
            self.dfs(amount, coins, sum + coins[i], i)
```

## 解法二：dp

`dp[i][j]` 的定义如下： 若只使用前 i 个物品（可以重复使用），当背包容量为 j 时，有`dp[i][j]` 种方法可以装满背包。 i=0表示不取，因此对coins从1开始遍历，i对应coins\[i-1] 状态转移：

```
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
			装入第i个      不装第i个
```

`dp[i][j]` 的值应该是以上两种选择的结果之和 base case：

```
dp[0][j]=0	#一个数都不取
dp[i][0]=1	#凑出0
```

第二条比较难理解，也是dp的关键。 为啥凑0也算一种凑法？例如5=0+5也算一种，因此`dp[i][0]=1`虽然第二个状态看上去是0，在迭代中实际操作是取**单个**第i个数，所以也算一种

```python
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n=len(coins)
        dp=[[0]*(amount+1) for _ in range(n+1)]
        for i in range(n+1):
            dp[i][0] = 1	#关键
        for i in range(1,n+1):
            for j in range(amount+1):
                if j-coins[i-1] >= 0:
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[n][amount] 
```