leetcode-mid-dynamic programming-322. Coin Change - NO

发布时间：2020-12-14 00:49:14 所属栏目：Linux 来源：网络整理

导读：mycode 我开始错误的思路：先用大钱除总钱数来保证?fewest number of coins，当最后剩下的amount小于最小币值的货币时，就说明return -1，但是这样想是有问题的！！！例如：[1,4,5]? ?12=5*2+2? ? 12 =5*2 + 1*2 用了4枚，但是12 = 4*3 因为还有下一步，也

mycode

我开始错误的思路：先用大钱除总钱数来保证?fewest number of coins，当最后剩下的amount小于最小币值的货币时，就说明return -1，但是这样想是有问题的！！！

例如：[1,4,5]? ?12=5*2+2? ? 12 =5*2 + 1*2 用了4枚，但是12 = 4*3

因为还有下一步，也就是用次大的币值去重复这个步骤！！而且也不能直接去使用次大的，而是先把最大币值的数目-1，-2，-3.。。。依次看

参考：

?

思路:类似于上一个62.unique paths，就要要考虑能到达该点的路径中的上一个点的情况

class Solution(object):
    def coinChange(self,coins,amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        n = len(coins)
        # dp[i]表示amount=i需要的最少coin数
        dp = [float("inf")] * (amount+1)
        dp[0] = 0
        for i in range(amount+1):
            for j in range(n):
                # 只有当硬币面额不大于要求面额数时，才能取该硬币
                if coins[j] <= i:
                    dp[i] = min(dp[i],dp[i-coins[j]]+1)
        # 硬币数不会超过要求总面额数，如果超过，说明没有方案可凑到目标值
        return dp[amount] if dp[amount] <= amount else -1

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!