# 518. Coin Change 2

{% embed url="<https://leetcode.com/problems/coin-change-2/>" %}

如果Q322是`bottom-up`写的，那这个其实就是改一点点，然而我是`top-down` `recursively`写的...

其实但就`coin change`这个来说，`bottom-up`还好写一些，不需要去想状态转换方程，直接当作`BFS/DFS`来想就可以。

```python
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = collections.defaultdict(int)
        dp[0] = 1
        
        for c in coins:
            for n in range(amount):
                dp[n+1] += dp[n+1-c]
        return dp[amount]
```
