# # 【LeetCode】518. Coin Change 2 解题报告（Python）

## # 题目描述：

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Note: You can assume that

1. 0 <= amount <= 5000
2. 1 <= coin <= 5000
3. the number of coins is less than 500
4. the answer is guaranteed to fit into signed 32-bit integer

Example 1:

``````Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
``````

Example 2:

``````Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
``````

Example 3:

``````Input: amount = 10, coins = [10]
Output: 1
``````

## # 解题方法

DP。第一感觉是完全背包问题，但其实由于没有重量和价值的对应关系，所以不一样。

``````class Solution(object):
def change(self, amount, coins):
"""
:type amount: int
:type coins: List[int]
:rtype: int
"""
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for i in range(1, amount + 1):
if coin <= i:
dp[i] += dp[i - coin]
return dp[amount]
``````