Leetcode322-零钱兑换

原题链接：https://leetcode-cn.com/problems/coin-change/

1、自顶向下

 1 class Solution(object):
 2     def coinChange(self, coins, amount):
 3         """
 4         :type coins: List[int]
 5         :type amount: int
 6         :rtype: int
 7         """
 8         if amount==0:
 9             return 0
10         if amount<0:
11             return -1
12         dp=[amount+1]*(amount+1)
13         dp[0]=0
14         for m in range(1,amount+1):
15             for n in range(len(coins)):
16                 if m>=coins[n]:
17                     dp[m]=min(dp[m],dp[m-coins[n]]+1)
18         if dp[amount]==amount+1:
19             return -1
20         else:
21             return dp[amount]