硬币变化问题的递推解法

Question

我需要编写一个算法，它接收一个数字和一个数字列表，并从列表中返回可能的数字组合的数量，从而可以创建和数。例如：def coin（5，[1,2,5,6]应该返回数字4，因为列表中有4种可能的组合可以一起创建数字5。下面是我尝试过的代码，但它不起作用。输出是6而不是4，我希望您能帮助我理解为什么。

def coin(n,lst):
    if n<=1:
        return 1
    else:
        total=0
        for i in range(len(lst)):
            change=lst[i]
            if change>n:
                continue
            else:
                result=coin(n-change,lst[i:])
                if result>0:
                    total+=result
        return total
print(coin(5,[1,2,5,6]))

Answer 1

int coinCount( int C[], int m, int n )

    {
        // if n is 0 return 1
        if (n == 0)
        return 1;

        // If n is less than 0 then no solution exists
        if (n < 0)
        return 0;

        // If there are no coins and n is greater than 0, then no solution exists
        if (m <=0 && n > 0)
        return 0;

        return coinCount( C, m - 1, n ) + coinCount( C, m, n-C[m-1] );
    }

Answer 2

错误在于基本情况：

    if n<=1:
        return 1

只有当1是允许的硬币之一时，此项才有效。但在递归的情况下，您将在lst[i:::处对列表进行切片，因此并非每次都允许使用所有硬币。有时，1不是允许使用的硬币之一，在这种情况下，有零种方法可以使总数为1，而不是一种方法。要解决此问题，请编写以下内容：

    if n <= 1:
        if n == 0 or n in lst:
            return 1
        else:
            return 0

这是正确的，因为您可以在基本情况下对n进行更改，如果n是0（我们总是可以使0），或者如果n是1并且1是允许的硬币之一。

也就是说，让递归大小写处理1会更简单，所以大小写只需要处理0；这也是正确的：

    if n == 0:
        return 1