使用memoization - Python3实现嵌套回溯功能

Question

我是编程新手，目前正在练习Leetcode问题。我正在使用回溯和memoization来解决其中一个问题。算法并不难理解，我的代码看起来像这样：

    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        def recursiveWithMem(S, i) -> int:
            if i == len(nums):
                return (1 if S == 0 else 0)

            key = (i, S)
            if key in mem:
                return mem[key]

            r = recursiveWithMem(S - nums[i], i + 1) + recursiveWithMem(S + nums[i], i + 1)
            mem[key] = r
            return r
        
        mem = {}
        return recursiveWithMem(S, 0)

当我查看其他人的提交时，他们会将mem作为函数的一个属性传递。它不会影响时间复杂度，但第二种方法使用15MB内存，而我的实现使用35MB。

def findTargetSumWays(self, nums: List[int], S: int) -> int:
        def recursiveWithMem(S, i, mem) -> int:
            if i == len(nums):
                return (1 if S == 0 else 0)

            key = (i, S)
            if key in mem:
                return mem[key]

            r = recursiveWithMem(S - nums[i], i + 1, mem) + recursiveWithMem(S + nums[i], i + 1, mem)
            mem[key] = r
            return r
        
        mem = {}
        return recursiveWithMem(S, 0, mem)

我也尝试了@cache，它使用了45MB的内存。我非常困惑为什么将memo传递到函数中可以帮助减少内存使用。请帮帮我！提前谢谢你！

Answer 1

看看发生了什么，你所做的mem的声明在函数声明的下面，所以你在函数中使用的mem与你在该函数的声明下声明的mem没有任何关系，它的作用域不是它的作用域，而是在每次调用函数时创建一个新的字典，正如你看到的15mb的代码，它已经传递了mem作为论据，确保不会为每个函数调用创建新的内存字典副本。我希望这能让事情变得更清楚。