leetcode 322 零钱兑换

通过动态规划方法，dp[amount]为金钱为amount时需要的最少硬币数目，状态转移公式，当最后一枚硬币是ci的时候，d[amount]=dp[amount-ci]+1,最后这枚硬币是多少需要遍历。

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:

        dp=[float('inf') for _ in range(amount+1)] 
        dp[0]=0

        for i in range(amount+1):
            for j in range(len(coins)):
                if i>=coins[j]:
                    dp[i]=min(dp[i-coins[j]]+1,dp[i])
        if dp[amount]==float('inf'):return -1

        return dp[amount]

通过记忆化递归，节省时间。

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        minvalue=float('inf')
        memo={}#注意使用字典
        #@functools.lru_cache(amount)
        def dfs(amount):
            if amount==0:           
                return 0
            if amount<0:
                return -1

            mini=float('inf')

            for i in range(len(coins)):
                if (amount-coins[i]) in memo:
                    res= memo[amount-coins[i]]
                else:
                    res=dfs(amount-coins[i])
                    memo[amount-coins[i]]=res
                print(res)
                if res>=0 and mini>res:#注意这个地方一层一层递归回来，所以会出现大于0的情况。
                    mini=res+1
            return mini if mini<float('inf') else -1


        return dfs(amount)