动态规划howSum的Python记忆化实现为何效率与暴力解法一致？

问题原因 #

你的记忆化缓存完全没有生效，核心原因是递归调用时没有传递memo参数：
当前代码中只有最外层调用会初始化memo字典，后续每一层递归调用都没有传入已经缓存了计算结果的memo对象，每次子递归都会重新生成全新的空memo，之前已经计算过的目标和结果完全没有被复用。当测试300的用例时，递归树会完全展开，运行效率和暴力解法一致。

修正方案 #

• 调整递归调用语句，补传memo参数：将remainderResult = howSum(remainder, nums)修改为remainderResult = howSum(remainder, nums, memo)
• 补全最后一行测试用例缺失的右括号，避免语法错误

修正后完整代码 #

def howSum(targetSum, nums, memo = None):
    if memo is None:
        memo = {}
        
    if targetSum in memo: return memo[targetSum]
    if targetSum < 0: return None
    if targetSum == 0: return []
    
    for num in nums:
        remainder = targetSum - num
        remainderResult = howSum(remainder, nums, memo)
        
        if remainderResult is not None:
            remainderResult.append(num)
            memo[targetSum] = remainderResult
            return memo[targetSum]
        
    memo[targetSum] = None
    return None

print(howSum(7, [2, 3])) # [3,2,2]
print(howSum(7, [5, 3, 4, 7])) # [4,3]
print(howSum(7, [2, 4])) # None
print(howSum(8, [2, 3, 5])) # [2,2,2,2]
print(howSum(300, [7,14])) # None

修改后最后一个测试用例可以秒返回结果。

内容的提问来源于stack exchange，提问作者Semeriuss