# coding=utf-8
# 递归
class Solution1(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
if not coins or amount <= 0:
return -1
self.res = amount
self.flag = False
self.tryChange(coins,amount,0)
if self.flag:
return self.res
else:
return -1
def tryChange(self,coins,amount,ans):
if amount == 0:
self.flag = True
self.res = min(self.res,ans)
if amount < 0:
return
for i in range(len(coins)):
self.tryChange(coins,amount-coins[i],ans+1)
# s = Solution1()
#
# coins = [1, 2, 5]
# amount = 11
#
# coins1 = [2]
# amount1 = 3
#
# print s.coinChange(coins1,amount1)
# 记忆化递归
class Solution2(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
if not coins or amount <= 0:
return -1
self.maxAmount = amount+1
return self.tryChange(coins,amount)
def tryChange(self,coins,amount):
if amount == 0:
return 0
res = amount
for i in range(len(coins)):
if amount - coins[i]>=0:
res = min(res,1 + self.tryChange(coins,amount-coins[i]))
return res
# 记忆化递归 返回值不纯粹2
class Solution3(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
if not coins or amount <= 0:
return -1
self.maxAmount = amount + 1
return self.tryChange(coins, amount)
def tryChange(self, coins, amount):
if amount == 0:
return 0
if amount < 0:
return -1
res = amount
for i in range(len(coins)):
value = self.tryChange(coins, amount - coins[i])
if value == -1:
continue
else:
res = min(res,1+value)
return res
# 记忆化递归 返回值不纯粹2
class Solution4(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
if not coins or amount <= 0: return -1 self.maxAmount = amount + 1 self.res = self.maxAmount return self.tryChange(coins, amount,0) def tryChange(self, coins, amount,ans): if amount == 0: return ans if amount < 0: return -1 res = self.maxAmount # res = amount for i in range(len(coins)): value = self.tryChange(coins, amount - coins[i],ans+1) if value == -1: continue else: res = min(res,value) return res# s = Solution4()## coins = [1, 2, 5]# amount = 11## coins1 = [2]# amount1 = 3## print s.coinChange(coins,amount)# 记忆化递归 返回值不纯粹2class Solution5(object): def coinChange(self, coins, amount): """ :type coins: List[int] :type amount: int :rtype: int """ if not coins or amount < 0: return -1 if amount == 0: return 0 self.maxAmount = amount + 1 self.memo = [-1 for i in range(amount+1)] self.res = self.tryChange(coins, amount) if self.res == self.maxAmount: return -1 else: return self.res def tryChange(self, coins, amount): if self.memo[amount] != -1: return self.memo[amount] if amount == 0: return 0 res = self.maxAmount # res = amount for i in range(len(coins)): if amount - coins[i] >=0: res = min(res,1+self.tryChange(coins, amount - coins[i])) self.memo[amount] = res return res# s = Solution5()## coins = [1, 2, 5]# amount = 11## coins1 = [2]# amount1 = 3## coins2 = [112,149,215,496,482,436,144,397,500,189]# amount2 = 8480### print s.coinChange(coins2,amount2)# 动态规划class Solution6(object): def coinChange(self, coins, amount): """ :type coins: List[int] :type amount: int :rtype: int """ if not coins or amount < 0: return -1 if amount == 0: return 0 maxAmount = amount + 1 memo = [maxAmount for i in range(amount+1)] memo[0] = 0 for i in range(1,amount+1): for j in coins: if i - j >=0: memo[i] = min(memo[i],memo[i-j]+1) if memo[amount] == maxAmount: return -1 return memo[amount]s = Solution6()coins = [1, 2, 5]amount = 11coins1 = [2]amount1 = 3coins2 = [112,149,215,496,482,436,144,397,500,189]amount2 = 8480print s.coinChange(coins2,amount2)
