为什么此解决方案在 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
如果您有什么不明白的地方,请给我留言:)
我正在学习有关动态规划的教程,但我正在努力在以下问题中实现记忆化:
* 编写一个名为 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
如果您有什么不明白的地方,请给我留言:)