python - 带有记忆的子集和

Question

对于家庭作业，我为子集总和编写了一个递归函数，但我找不到字典的正确键，我一直收到键错误。不是在寻找解决方案，只是可以帮助我理解磨损的解释：

def subset_sum(s, numbers):
    memo={}
    return subset_sum_memo(s, numbers, 1, memo)

def subset_sum_memo(s, numbers, i, memo):
    key= (len(numbers))
    if key not in memo:
        if s==0:
            memo[key]= True
        elif s<0 or numbers==[]:
            memo[key]= False
        for n in range(len(numbers)):
            if subset_sum_memo(s - numbers[n], numbers[:n] + numbers[n+1:], n, memo):
                memo[key]= True
    return memo[key]

我得到的错误是：

if subset_sum_memo(s - numbers[n], numbers[:n] + numbers[n+1:], n, memo): 
File "C:\Users\Yarden\Desktop\Python\302154513_ex11_q1.py", line 17, in subset_sum_memo return memo[key] KeyError: 6

更新 1

这是我的新代码：

def subset_sum(s, numbers):
    memo={}
    return subset_sum_memo(s, numbers, 1, memo)


def subset_sum_memo(s, numbers, i, memo):
    key= (len(numbers))
    if s==0:
        memo[key]= True
    if s<0 or numbers==[]:
        memo[key]= False
    if key not in memo:
        for n in range(len(numbers)):
            if subset_sum_memo(s - numbers[n], numbers[:n] + numbers[n+1:], n, memo):
                memo[key]= True
            else:
                memo[key]=False
    return memo[key]

还是有问题，不知道为什么

Answer 1

change elif s<0 or numbers==[]: to elif s<0 or isinstance(numbers,list):

Answer 2

这是你的代码：

if key not in memo:
    if s==0:
        memo[key]= True
    elif s<0 or numbers==[]:
        memo[key]= False
    for n in range(len(numbers)):
        if subset_sum_memo(s - numbers[n], numbers[:n] + numbers[n+1:], n, memo):
            memo[key]= True
return memo[key]

问题是，您正在检查是否key不在memo并进入该块。然后你有多个条件但不是默认情况。

如果所有条件都是false，则不会为 设置值memo[key]。