python-3.x - 硬币找零问题 - 使用记忆 - 不工作

Question

硬币找零问题 - 试图获得最大数量的选项来进行找零。因此，使用记忆化编写了一个代码，但它只能在 n=980 之前工作。但是当我试图让一个更大的 n python 停止运行时 - “RecursionError：比较中超出了最大递归深度”。

我该如何解决？

def find_num_changes_mem(n, lst, memo=None):
if n==0:
    return 1
if n<0 or lst==[]:
    return 0
if memo==None:
    memo={}
if (n,len(lst)) in memo:
    return memo[(n,len(lst))]
else:
    if lst[0]>n:
        memo[(n,len(lst))]=find_num_changes_mem(n,lst[1:],memo)
    else:
        memo[(n,len(lst))]=find_num_changes_mem(n-lst[0],lst[0:],memo)+find_num_changes_mem(n,lst[(1):],memo)
return memo[(n,len(lst))]

标签： python-3.xmemoizationcoin-change