# 518. Coin Change II

[https://leetcode.com/problems/coin-change-ii/](https://leetcode.com/problems/coin-change-ii/)

## solution

* 完全背包
  * 01背包和完全背包区别在于，对背包遍历顺序是右到左，还是左到右
  * 注意遍历顺序，物品还是背包决定了结果是排列还是组合

```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)):
            for j in range(coins[i], amount+1):
                dp[j] += dp[j-coins[i]]
        return dp[amount]
```

时间复杂度：O(|coins|⋅amount)\
空间复杂度：O(amount)
