我正在关注这个关于动态编程的教程,我正在努力在以下问题中实现内存:
*写一个函数叫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 如何处理默认参数引起的。来自文章:
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!
关于javascript - 为什么这个解决方案在 Javascript 中有效,但在 Python 中无效? (动态编程),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65428535/