## 题目描述：

LeetCode 518. Coin Change 2

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

• 0 <= amount <= 5000
• 1 <= coin <= 5000
• the number of coins is less than 500
• 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
```

## 题目大意：

1. 0 <= amount <= 5000
2. 1 <= coin <= 5000
3. 硬币个数不超过500
4. 答案确保在32位整数范围内

## Python代码：

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

```比如用面值{1, 2, 5}的硬币组成总额5元的不重复排列共9种，分别为：

[1,1,1,1,1] [1,1,1,2] [1,1,2,1] [1,2,1,1] [2,1,1,1] [1,2,2] [2,1,2] [2,2,1] [5]```

## Python代码：

``````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 x in range(amount + 1):
for c in coins:
if c > x: continue
dp[x] += dp[x - c]
return dp[amount]
``````

Pingbacks已关闭。

1. youke 发布于 2017年2月13日 19:08 #

楼主能不能讲下，什么叫不同硬币的排列数

2. 在线疯狂 发布于 2017年2月13日 20:46 #

比如用面值为{1, 2, 5}的硬币组合为总额5元的不重复排列共9种，分别为：[1,1,1,1,1] [1,1,1,2] [1,1,2,1] [1,2,1,1] [2,1,1,1] [1,2,2] [2,1,2] [2,2,1] [5]

3. 西雅图 发布于 2017年3月7日 08:24 #

楼主，你的意思是“排列”里面order makes difference。比如，[2,1,2]和[2,2,1]是不一样的。这比较奇怪。当然如果题目是这样的要求那也没办法。