为什么这个解决方案可以在Java中运行，但不能在Python中运行？(动态规划) [英] Why does this solution work in Javascript but not in Python? (Dynamic programming)

问题描述

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

*编写一个名为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

推荐答案

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

这篇关于为什么这个解决方案可以在Java中运行，但不能在Python中运行？(动态规划)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！