时间戳

首页 > 解决方案 > 使用 memoization 实现嵌套回溯功能 - Python3

python-3.x - 使用 memoization 实现嵌套回溯功能 - Python3

问题描述

我是编程新手，目前正在练习 Leetcode 问题。我正在使用带有记忆的回溯解决其中一个问题。算法不难理解，我的代码是这样的：

    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 内存。我很困惑为什么将备忘录传递给函数可以帮助减少内存使用。请帮忙！先感谢您！

标签： python-3.x

解决方案

看看发生了什么，您所做的 mem 声明位于函数声明下方，因此您在函数内部使用的 mem 与您在该函数声明下方声明的 mem 无关，它不是作用域而是它每次使用每个函数调用创建一个新字典时，您所看到的 15 mb 的代码已将 mem 作为参数传递，确保不会为每个函数调用创建 Mem 字典的新副本。我希望这能让事情变得更清楚。

推荐阅读