javascript - 为什么 howSum 解决方案在 Javascript 中有效，但在 Python 中无效？（动态编程）

Question

这是Stack Overflow 上提出的这个问题的后续。

编写一个函数“howSum(targetSum, numbers)”，它接受一个 targetSum 和一个数字数组作为参数。

该函数应该返回一个数组，其中包含任何元素的组合，这些元素的总和正好是 targetSum。

如果没有组合到 targetSum，则返回 None。如果可能有多种组合，您可以返回任何一种。

我的解决方案的记忆python代码如下：

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)
        
        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

该算法有效，但对于最终的测试用例效率不高。实际上，运行时效率与蛮力解决方案没有什么不同。有什么问题？

标签： javascriptpythonpython-3.xdynamic-programmingmemoization

Answer 1

您似乎没有将memo值传递给递归howSum(remainder, nums)调用，因此您失去了在那里记忆的好处。