记忆化实践

Question

我正在 Python 进行记忆练习。对递归函数的前 4 次调用立即得到解决，但最后一次调用需要很长时间才能计算出我要记住的内容。我尝试的记忆代码的输出立即解决了前 4 个调用，但最后一个调用仍然花费相同的时间来计算。我的记忆代码中有没有实现错误的地方？感谢您的帮助，谢谢！

提示： 编写一个函数'howSum(targetSum, numbers)'，接受一个 targetSum 和一个数字数组作为参数。该函数应该 return 一个数组，其中包含加起来恰好等于 targetSum 的元素的任意组合。如果没有组合加起来等于 targetSum，则 return 为 null。如果有多种可能的组合，您可以 return 任意一种。

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

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

    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) 如您所知，它是递归的。

Answer 2

一些问题：

第一个函数被第二个覆盖，所以你实际上只用到第二个。因此，没有记忆发生
作业说你的函数应该接受一个数组，但你给它提供了一个集合。 {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, {})

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

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]))

记忆化实践

Memoization Practice

python

algorithm

memoization

dynamic-programming

python-3.x