javascript - 为什么这个解决方案在 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

标签： javascriptpythonpython-3.xdynamic-programming

Answer 1

感谢@Jared Smith 分享的文章，我能够弄清楚。

问题是由 python 如何处理默认参数引起的。来自文章：

在 Python 中，当在函数中将可变值作为默认参数传递时，只要该值发生突变，默认参数就会发生突变。

我的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!