为什么记忆在这个 Python 代码中不起作用？

Question

我正在关注动态规划视频。但是，我的代码的记忆不起作用。当我打印（备忘录）它是空白时，它不存储任何 True/False。请指教

def cansum(targetsum,numbers):
      memo = dict()
      print(memo)
      # check in memory
      if targetsum in memo:
            return memo[targetsum]
      if targetsum < 0: return False
      if targetsum == 0: return True
      for number in numbers:
            remainder = targetsum - number
            if cansum(remainder,numbers) == True:
                  memo[targetsum] = True
                  return True
      memo[targetsum] = False
      return False


print(cansum(7,[2,3])) #True
print(cansum(7,[5,3,4,7])) #True

Answer 1

我想这就是你想要做的：

def cansum(targetsum, numbers):
    memo = dict()

    def cansum_helper(targetsum, numbers):
        # check in memory
        if targetsum in memo:
            return memo[targetsum]
        if targetsum < 0:
            return False
        if targetsum == 0:
            return True
        for number in numbers:
            remainder = targetsum - number
            if cansum_helper(remainder, numbers) == True:
                memo[targetsum] = True
                return True
        memo[targetsum] = False
        return False

    result = cansum_helper(targetsum, numbers)

    print(memo)

    return result


print(cansum(7, [2, 3]))  # True
print(cansum(7, [5, 3, 4, 7]))  # True

如果你把

memo = dict()

进入递归函数，你为每个递归函数创建一个dict，一旦设置了备忘录，return语句就会随之而来，所以你不会能够看到变化。但目的是你只需要一个字典来完成你的整个功能。

为什么记忆在这个 Python 代码中不起作用？

why doesn't memoization work in this Python code?

python

memoization