使用递归计算的最小硬币数量

Question

这个问题是最流行的动态规划问题，如下所示。我们有无限面值的1、3和5的硬币。我们要用最少的硬币数得到N

我知道动态规划方法，在这种方法中，我们从基本情况建立一个解决方案。但我想知道如何编写一个纯递归的解决方案。我能很容易地用手算出N=11和面额=1,3,5]的数值。但由于某些原因，我无法完成以下工作。在

    def minNumberOfCoins(amount, denominations):
        if amount <= 0:
            return(0)
        if amount in denominations:
            return(1)
        else:
            listToExamine = list(filter(lambda x: x > 0, map(lambda x: amount - x, denominations)))
            print(listToExamine)
            minVal = min(listToExamine, key=lambda x: 1 + minNumberOfCoins(x, denominations))
            return(minVal)

据我所知，这个逻辑和我在纸上得出的结论是一致的。在Python的递归中是否有一些我不知道的细微差别，或者是我遗漏了一些微妙的东西？谢谢您！在

Answer 1

这种实现似乎更直接：

def minNumberOfCoins(amount, denominations):

    if amount <= 0:
        return(0)

    if amount in denominations:
        return(1)

    for d in sorted(denominations, reverse=True):
        if d <= amount:
            return 1 + minNumberOfCoins(amount - d, denominations)

Answer 2

更具可读性的方法。您不应该将map或{}与lambdas混合太多。条件理解和生成器通常是更好的选择：

def min_coins(amount, denominations):
    # these two base cases seem to cover more edge cases correctly
    if amount < 0:
        return None
    if amount == 0:
        return 0
    tries = (min_coins(amount-d, denominations) for d in denominations)
    try:
        return 1 + min(t for t in tries if t is not None)
    except ValueError:  # the generator in min produces no values
        return None   

min_coins(11, [1,3,5])
# 3