为什么此解决方案适用于 Javascript 而不适用于 Python？（动态编程）

马丁·谢尔

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

*编写一个函数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

对象浆果

你的储蓄机制有错误。

第一次调用函数时：

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

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

现在我们将检查第三次调用：

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

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

if targetSum in memo:
    return memo[targetSum]

并且因为从第 1 次呼叫开始，您的字典中已经有数字 7，它会搜索它并返回其值 - 从第 1 次呼叫开始，数字 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 封装到元组中并使用该元组作为键。
这就是该 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

如果你不明白什么，给我写评论:)

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。