python中的硬币兑换leetcode

Question

我试图自己解决LeetCode问题322。硬币兑换：

您将获得一个整数数组，表示不同面额的硬币，以及一个整数金额，表示总金额。

返回您需要的最少数量的硬币，以弥补该金额。如果这些硬币的任何组合都无法弥补这一数额，则返回-1。

你可以假设每种硬币的数量是无限的。

我似乎有一个错误，无法找出它。

我用DFS解决，基本上是说当目标达到0时，只需将所有的num聚集在一个数组中，并动态地保持尽可能短的结果。这是问题的决策树：

这是我的解决方案：

from typing import List
class Solution:
    def coinChange(self, nums: List[int], target: int) -> int:      
        def dfs(remainder):
            if remainder<0:
                return None
            if remainder==0:
                return []         
            shortest_combination=None
            for num in nums:
                print("target",remainder)
                print("num",num)             
                result=dfs(remainder-num)
                if result!=None:                    
                    combination=[*result,num]                    
                    if shortest_combination==None or len(combination)<len(shortest_combination):                        
                        shortest_combination=combination                    
            return shortest_combination       
        return -1 if dfs(target)==None else len(dfs(target))
    
        
    
s=Solution()
s.coinChange([1,2,5],100)

我打印num和余数，我发现由于某种原因余数从未达到0。基于DFS，如果我继续从100中减去1，我应该达到0，但不知何故，它没有达到任何num。

Answer 1

你的算法是正确的，它确实达到了0，但是在这种情况下你不打印它（函数在打印前退出）。添加更多调试，您会看到它确实到达了基本情况，并回溯并正确标识了子解决方案。

真正的问题是，您使用DFS访问的树是指数级的，因此您可以多次解决相同的问题。如果您添加几行代码来实现记忆化，您将看到它完成了这项工作：

from typing import List

class Solution:
    def coinChange(self, nums: List[int], target: int) -> int:
        memo = {}  # used for memoization
        def dfs(remainder):
            if remainder in memo:  # already solved this problem?
                return memo[remainder]  # then return what we got last time
            if remainder<0:
                return None
            if remainder==0:
                return []         
            shortest_combination=None
            for num in nums:
                result = dfs(remainder-num)
                if result!=None:
                    combination=[*result,num]
                    if shortest_combination==None or len(combination)<len(shortest_combination):
                        shortest_combination=combination                    
            memo[remainder] = shortest_combination  # memoize this solution
            return shortest_combination

        return -1 if dfs(target)==None else len(dfs(target))


s=Solution()
print(s.coinChange([1,2,5],100))  # 20

Answer 2

这个问题需要用动态规划来解决。给定任何value，假设您已经计算了生成0的最小数量的硬币，...value-1，要计算value的最小数量的硬币，请查看value-coin1，value-coin2，value-coin3，...，选择最小的，并添加一个。

实际上，编码这是你应该自己做的事情。