为什么此解决方案在 Javascript 中有效,但在 Python 中无效? (动态规划)

Why does this solution work in Javascript but not in Python? (Dynamic programming)

我正在学习有关动态规划的教程,但我正在努力在以下问题中实现记忆化:

* 编写一个名为 canSum(targetSum, numbers) 的函数,仅当数组中的数字总和为目标总和时才 returns 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 做了以下操作,这正是讲师正在做的,但它只是 returns 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

多亏了@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!

你的保存机制有bug。

第一次调用函数时:

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

此调用将 return 为真,它将在字典中创建值为真(7:真)的键。
这就是它不起作用的原因

现在我们将检查第 3 个调用:

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

你的函数做的第一件事是检查数字 7 是否在字典中:

if targetSum in memo:
    return memo[targetSum]

并且因为从第一次调用开始,您已经在字典中找到了数字 7,它会搜索它并 return 它的值 - 从第一次调用开始,数字 7 的值是 True

这是第一次调用前后的字典。

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

第一次调用后,此字典将 return 每次调用带有数字 7 的函数时都为真。
并且因为 Python 共享默认参数(Jared Smith 在评论中对此进行了解释),每次调用都会 return True for number 7

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

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

第一种方式: 将 targetSum 和 nums 封装到元组中,并将该元组用作键。
这就是 dict 的样子

{
  (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

您还必须将 list 转换为 tuple ,因为 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

如果您有什么不明白的地方,请给我留言:)