回忆录实践

Question

我正在用Python进行记忆练习。递归函数的前4个调用立即得到了解决，但最后一个调用的计算时间太长，这正是我想要记住的。我尝试的记忆代码的输出立即解决了前4个调用，但最后一个调用仍然需要相同的计算时间。在我的记忆代码中是否有我实现的错误？谢谢你的帮助，谢谢

提示：编写一个函数“howSum（targetSum，numbers）”，该函数接受targetSum和数字数组作为参数。函数应返回一个数组，该数组包含与targetSum相加的元素的任意组合。如果没有与targetSum相加的组合，则返回null。如果可能有多个组合，可以返回任意一个组合

以下是我对记忆代码和递归函数的实现，以供快速参考：

def howSum(target_num, listt, memo={}):
#if target_num in memo: return memo[target_num]
    if target_num == 0: return []
    if target_num < 0: return None
    for num in listt:
        remainder = target_num - num
        remainder_result = howSum(remainder, listt, memo)
        if remainder_result is not None:
            memo[target_num]= *remainder_result, num
            return memo[target_num]
    memo[target_num] = None
    return None

def howSum(target_num, listt):
    if target_num == 0: return []
    if target_num < 0: return None
    for num in listt:
        remainder = target_num - num
        remainder_result = howSum(remainder, listt)
        if remainder_result is not None:
            return *remainder_result, num
    return None

print(howSum(7, {2, 3}))
print(howSum(7, {5, 3, 4, 7}))
print(howSum(7, {2, 4}))
print(howSum(8, {2, 3, 5}))
print(howSum(300, {7, 14}))

Answer 1

一些问题：

• 第一个函数被第二个函数覆盖，因此实际上只使用第二个函数。因此，没有发生回忆录
• 赋值说明您的函数应该接受一个数组，但您提供了一个集合{2, 3}是Python中的一个集合，而[2, 3]是一个列表

如果使用了第一个功能：

• 它有一个实际需要的注释行
• 它接受一个用={}初始化一次（仅一次！）的参数。这意味着如果主代码进行多个调用（如示例中所示），memo将不会在调用之间重置，因此结果将是错误的

因此，为第一个函数使用不同的名称，并删除memo的初始值。避免在第二个函数中重复代码，让它调用第一个函数，确保它传递一个空的memo字典：

def howSumRec(target_num, listt, memo):
    if target_num in memo: 
        return memo[target_num]
    if target_num == 0:
        return []
    if target_num < 0: 
        return None
    for num in listt:
        remainder = target_num - num
        remainder_result = howSumRec(remainder, listt, memo)
        if remainder_result is not None:
            memo[target_num]= *remainder_result, num
            return memo[target_num]
    memo[target_num] = None
    return None

def howSum(target_num, listt):
    return howSumRec(target_num, listt, {})

如果需要，您仍然可以对此进行改进，因为这没有利用添加术语的顺序并不重要这一事实。因此，您可以确保递归调用不会查看列表中比添加的上一个术语更早的术语：

def howSumRec(target_num, listt, i, memo):
    if target_num in memo: 
        return memo[target_num]
    if target_num == 0:
        return []
    if target_num < 0: 
        return None
    for j in range(i, len(listt)):
        num = listt[j]
        remainder = target_num - num
        remainder_result = howSumRec(remainder, listt, j, memo)
        if remainder_result is not None:
            memo[target_num]= *remainder_result, num
            return memo[target_num]
    memo[target_num] = None
    return None

def howSum(target_num, listt):
    return howSumRec(target_num, listt, 0, {})

重要的是，在这个版本中，listt实际上是一个列表，而不是一个集合，因此将其称为：

print(howSum(7, [2, 3]))
print(howSum(7, [5, 3, 4, 7]))
print(howSum(7, [2, 4]))
print(howSum(8, [2, 3, 5]))
print(howSum(300, [7, 14]))

Answer 2

    for num in listt:
        remainder = target_num - num
        remainder_result = howSum(remainder, listt)
        if remainder_result is not None:
            return remainder_result, num

由于此代码，操作计数为：2^（300/14）~2^（300/7） 正如你所知，它是递归的