为什么这个解决方案可以在Javascript中工作而不能在Python中工作？（动态规划）

Question

我正在学习关于动态编程的本教程，我正在努力实现以下问题的记忆化：

*编写一个名为canSum(targetSum, numbers)的函数，仅当数组中的数字可以求和到目标和时才返回True。数组中的所有数字都是正整数，可以多次用于求解

例如：

canSum(7, [2, 4]) -> False因为不能通过添加2和4来形成7。*

我的暴力解决方案如下：

def canSum(targetSum, numbers):
    if targetSum == 0:
        return True
    if targetSum < 0:
        return False

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

    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

效果很好，但如果我们记下余数的解决方案，速度会更快（视频1:28:03分对此进行了解释）。我用Python做了以下操作，这正是讲师正在做的，但它只返回True，我不明白为什么

def canSum(targetSum, numbers, 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]))
print(canSum(7, [5, 3, 4, 7]))
print(canSum(7, [2, 4]))
print(canSum(8, [2, 3, 5])) # All of them return True

Answer 1

@Martin Schere，你可以试试这个片段，看看是否有帮助： （很好的一点是，您可以轻松修改以返回两个数字的索引。这是一个两和问题）

实际上，在这种情况下，记忆可以通过使用dict（）来记录和跟踪所有的数字，并检查差异来实现。假设目标数为正数，nums数组包含多个数字

```python
def canSum(target, nums):
    dd = {}
    ans = []
        
    for i, num in enumerate(nums):
        if (target-num) not in dd:
            dd[num] = i
        else:
            ans = [dd[target-num], i]
            
    return True if ans else False
        
        
print(canSum(7, [2, 3, 4]))    # True
print(canSum(7, [5, 3, 4, 7])) # True
print(canSum(7, [2, 4]))    # False
print(canSum(8, [2, 3, 5])) # True

Answer 2

你有错误

第一次调用函数时：

print(canSum(7, [2, 3]))

此调用将返回true，并将在字典中创建值为true（7:true）的键。
这就是它不起作用的原因

现在我们将检查第三次呼叫：

print(canSum(7, [2, 4]))

函数要做的第一件事是检查字典中是否有数字7：

if targetSum in memo:
    return memo[targetSum]

因为从第一次调用开始，字典中就有数字7，它将搜索它并返回它的值——从第一次调用开始，数字7的值为True

这是第一次通话前后的字典

{}                                    # before first call
{1: False, 3: True, 5: True, 7: True} # after first call

第一次调用后，每次调用数字为7的函数时，此字典都将返回True。
而且，由于Python共享默认参数（Jared Smith在注释中对此进行了解释），所以对于数字7，每个调用都将返回True

如何解决这个问题？ 必须将targetSum和nums保存到字典中，并测试这两个值

有两种方法可以做到这一点：

第一条路： 将targetSum和nums封装到tuple中，并将该tuple用作键。
这就是那条命令的样子

{
  (7, (2, 3)) : True,
  (7, (5, 3, 4, 7)) : True,
  (7, (2, 4)) : False
}

这是对以下各项的实施：

keyTuple = (targetSum, tuple(numbers))
if keyTuple in memo:
    return memo[keyTuple]

if targetSum == 0:
    return True
if targetSum < 0:
    return False

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

memo[keyTuple] = False
return False

您还必须将列表转换为元组，因为python不允许列表作为字典的键

第二种方法是使用字典中的字典。 像这样的

{
 7: {
   (2,3): True,
   (5, 3, 4, 7): True
   (2,4): False
 }

}

这是执行：

def canSum(targetSum, numbers, memo={}):
numbersTuple = tuple(numbers)

if targetSum in memo:
    targetDict = memo[targetSum]
    if numbersTuple in targetDict:
        return targetDict[numbersTuple]
else:
    memo[targetSum] = {}

if targetSum == 0:
    return True
if targetSum < 0:
    return False

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

targetDict = memo[targetSum]
targetDict[numbersTuple] = False
return False

如果你不明白，给我写评论：）

Answer 3

多亏了@Jared Smith分享的文章，我才明白这一点

这个问题是由python如何处理默认参数引起的。从文章中：

In Python, when passing a mutable value as a default argument in a function, the default argument is mutated anytime that value is mutated.

我的memo字典每次调用都会发生变异。因此，我只是更改了memo=None，并添加了一个检查，以查看它是否是函数的第一次调用：

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 -> Works fast with large inputs!