改变Python(相比之下，最大递归深度超过)

Question

因此，我对有时有效的变更问题有递归解决方案。是：

def change(n, c):
   if (n == 0):
      return 1
   if (n < 0):
      return 0;
   if (c + 1 <= 0 and n >= 1):
      return 0
   return change(n, c - 1) + change(n - coins[c - 1], c);

硬币是我的硬币数组。例如[1,5,10,25]。n是硬币的量，例如1000，C是硬币阵列的长度-1。该解决方案在某些情况下起作用。但是，当我需要在两秒钟内运行时，我会使用：

coins: [1,5,10,25]
n: 1000

我得到一个：

RecursionError: maximum recursion depth exceeded in comparison

所以我的问题是，如何优化它的最佳方法。使用某种流量控制？我不想做类似的事情。

# Set recursion limit
sys.setrecursionlimit(10000000000)   

更新：

我现在有类似

的东西

def coinss(n, c):
   if n == 0:
      return 1
   if n < 0:
      return 0
   nCombos = 0
   for c in range(c, -1, -1):
      nCombos += coinss(n - coins[c - 1], c)

   return nCombos

，但它需要永远。在一秒钟内进行此运行是理想的。

Answer 1

如上所述，您可以使用dp进行更最佳的解决方案。还有您的条件检查 - if (c + 1 <= 0 and n >= 1)

应该是

if (c <= 1 ):

，n将始终为> = 1和c＆lt; = 1，如果硬币数小于或等于1。

Answer 2

使用递归时，您将始终遇到此内容。如果将递归限制设置为更高，则可以在更大的数字上使用算法，但是您将始终受到限制。递归限制可防止您获得堆栈溢出。

解决更大变化量的最佳方法是将迭代方法交换。Wikipedia有算法：https://en.wikipedia.org/wiki/change-making_problem

Answer 3

请注意，您这里有一个错误：

if (c + 1 <= 0 and n >= 1):

就像

if (c <= -1 and n >= 1):

所以c可以是0并传递到下一步，您将c-1传递给索引，这是因为Python不介意负面索引，但仍然false(coins[-1]产生25(，因此您的解决方案有时会打印1组合太多了。

我已经用递归和堆栈方法重写了您的算法：

递归(固定，在Init上不需要c，这要归功于一种内部递归方法，但仍溢出堆栈(：

coins = [1,5,10,25]
def change(n):
    def change_recurse(n, c):
       if n == 0:
          return 1
       if n < 0:
          return 0;
       if c <= 0:
          return 0
       return change_recurse(n, c - 1) + change_recurse(n - coins[c - 1], c)
    return change_recurse(n,len(coins))

迭代/堆栈方法(不是动态编程(，不反复，只使用"堆栈"来存储执行的计算：

def change2(n):
    def change_iter(stack):
        result = 0
        # continue while the stack isn't empty
        while stack:
            # process one computation
            n,c = stack.pop()
            if n == 0:
              # one solution found, increase counter
              result += 1
            if n > 0 and c > 0:
                # not found, request 2 more computations
                stack.append((n, c - 1))
                stack.append((n - coins[c - 1], c))
        return result
    return change_iter([(n,len(coins))])

这两种方法都返回n低值的相同值。

for i in range(1,200):
    a,b = change(i),change2(i)
    if a != b:
        print("error",i,a,b)

上面的代码在没有任何错误打印的情况下运行。

现在print(change2(1000))需要几秒钟，但打印142511而不会吹堆栈。