Python字典get与in操作在动态规划canSum代码中的表现差异问题

在编写基于动态规划递归思想的canSum函数时，替换缓存判断逻辑后出现大输入下性能陡降的问题，两版代码仅缓存判断行存在差异：

第一版（性能正常） #

使用targetSum in memo判断缓存是否命中，大输入下运行速度快：

def canSum(targetSum, numbers, memo=None):
    if memo == None:
        memo = {}

    if targetSum in memo:
        return memo[targetSum]
    if targetSum == 0:
        return True
    if targetSum < 0:
        return False

    for n in numbers:
        remainder = targetSum - n
        if canSum(remainder, numbers, memo):
            memo[targetSum] = True
            return True

    memo[targetSum] = False
    return False


print(canSum(7, [2, 3])) # True
print(canSum(7, [5, 3, 4, 7])) # True
print(canSum(7, [2, 4])) # False
print(canSum(8, [2, 3, 5])) # True
print(canSum(3000, [7, 14])) # False -> 大输入下运行速度很快

第二版（大输入超时） #

将缓存判断替换为if memo.get(targetSum,False)后，小输入结果正常，targetSum=3000场景下持续运行无输出：

def canSum(targetSum, numbers, memo=None):
    if memo == None:
        memo = {}

    if memo.get(targetSum,False):
        return memo[targetSum]
    if targetSum == 0:
        return True
    if targetSum < 0:
        return False

    for n in numbers:
        remainder = targetSum - n
        if canSum(remainder, numbers, memo):
            memo[targetSum] = True
            return True

    memo[targetSum] = False
    return False


print(canSum(7, [2, 3])) # True
print(canSum(7, [5, 3, 4, 7])) # True
print(canSum(7, [2, 4])) # False
print(canSum(8, [2, 3, 5])) # True
print(canSum(3000, [7, 14])) # False -> 持续运行无输出

两者的判断逻辑本质完全不同：

• targetSum in memo判断的是键是否存在于字典中，和键对应的值无关。只要目标值已经被计算过（无论结果是True还是False），都会直接返回缓存结果，避免重复计算，符合动态规划缓存的设计预期。
• memo.get(targetSum,False)是先取键对应的值，再判断该值是否为真。当某个目标值的计算结果是False被存入缓存后，get调用会返回False，触发if判断不通过，程序不会走缓存返回的逻辑，会重新递归计算该目标值的结果。相当于所有结果为False的目标值都没有用上缓存，时间复杂度直接退化为无缓存的递归版本，大输入下自然会出现超时。

以memo = {7:False}为例：

• 7 in memo返回True，会直接返回缓存的False，不需要重复计算
• memo.get(7,False)返回False，if条件不成立，程序会重新执行7的计算逻辑

如果要使用get实现和in相同的缓存判断逻辑，可以调整判断逻辑为判断键是否存在，而非判断值是否为真，或者用特殊标记代表未计算的状态，比如：

# 方案1：判断get返回是否为默认的未计算标记
res = memo.get(targetSum, None)
if res is not None:
    return res

内容的提问来源于stack exchange，提问作者T S Aditya