为什么 howSum 解决方案在 Javascript 中有效，但在 Python 中无效？ （动态规划）

Question

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

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

该函数应该 return 一个数组，其中包含加起来正好等于 targetSum 的元素的任意组合。

如果没有组合加起来等于targetSum，则returnNone。如果有多种可能的组合，您可以 return 任意一种。

我记忆的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

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

Answer 1

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

Answer 2

递归调用的时候传个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 ) #pass memo as well
    
    if remainderResult is not None:
        remainderResult.append(num)
        memo[targetSum] = remainderResult
        return memo[targetSum]
    
memo[targetSum] = None
return None

Answer 3

我认为您没有传递答案数组，这就是它不起作用的原因。试试这个代码：

hmap = {}
def howSum(targetSum, numbers,ans=[]):
    if targetSum == 0:
        return ans
    if targetSum <0:
        return None
    if targetSum in hmap:
        return hmap[targetSum]
    for len in numbers:
        remainder = targetSum-len
        remainder_result = howSum(remainder,numbers,ans)
        if remainder_result != None:
            hmap[remainder]  = remainder_result
            ans.append(len)
            return ans
    return None