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:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
My code:
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
if amount==0:
return 0
if amount<0:
return -1
self.record=[-2]*amount
result=self.check_coin(coins,amount)
return result
def check_coin(self,coins,amount):
if amount==0:
return 0
if amount<0:
return -1
if self.record[amount-1]!=-2:
return self.record[amount-1]
min_value=9999999999
for coin in coins:
res=self.check_coin(coins,amount-coin)
if res>=0 and res<min_value:
min_value=1+res
if min_value!=9999999999:
self.record[amount-1]=min_value
else:
self.record[amount-1]=-1
return self.record[amount-1]