# leetcode Coin Change

### leetcode Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return `-1`.

Example 1:
coins = `[1, 2, 5]`, amount = `11`
return `3` (11 = 5 + 5 + 1)

Example 2:
coins = ``, amount = `3`
return `-1`.

Note:
You may assume that you have an infinite number of each kind of coin.

dp，设dp[i] 为兑换目标i最少的硬币数。

java 22ms

C++ 120ms

python

### 5 thoughts on “leetcode Coin Change”

1. nanjiwubing says:

该方法报错。

• hrwhisper says:

感谢提出已修改 leetcode又加数据了- -|

2. Tom says:

Hi,
Your Java code does not handle the following input:

1

• hrwhisper says:

You are right.
I just guess the max number will not greater than 0x7ffffffe(2147483646), so if the number greater than it(2147483647), it wil be overflow.
Now, I use 0x7fffffff(2147483647) as maximum number, and add dp[i]!= INF for condition judge.
Thanks~