```
class Solution(object):
def coinChange(self, coins, amount):
if amount == 0: return 0
if not coins: return -1
maxval = 99999
dp = [maxval for i in xrange(amount+1)]
dp[0] = 0
for v in xrange(1, amount+1):
for c in coins:
if c <= v:
dp[v] = min(dp[v], 1+dp[v-c])
if dp[amount] == maxval: return -1
return dp[amount]
```