我正在学习关于动态编程的本教程,我正在努力实现以下问题的记忆化:
*编写一个名为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
@Martin Schere,你可以试试这个片段,看看是否有帮助: (很好的一点是,您可以轻松修改以返回两个数字的索引。这是一个两和问题)
实际上,在这种情况下,记忆可以通过使用dict()来记录和跟踪所有的数字,并检查差异来实现。假设目标数为正数,nums数组包含多个数字
你有错误
第一次调用函数时:
此调用将返回true,并将在字典中创建值为true(7:true)的键。
这就是它不起作用的原因
现在我们将检查第三次呼叫:
函数要做的第一件事是检查字典中是否有数字7:
因为从第一次调用开始,字典中就有数字7,它将搜索它并返回它的值——从第一次调用开始,数字7的值为True
这是第一次通话前后的字典
第一次调用后,每次调用数字为7的函数时,此字典都将返回True。
而且,由于Python共享默认参数(Jared Smith在注释中对此进行了解释),所以对于数字7,每个调用都将返回True
如何解决这个问题? 必须将targetSum和nums保存到字典中,并测试这两个值
有两种方法可以做到这一点:
第一条路: 将targetSum和nums封装到tuple中,并将该tuple用作键。
这就是那条命令的样子
这是对以下各项的实施:
您还必须将列表转换为元组,因为python不允许列表作为字典的键
第二种方法是使用字典中的字典。 像这样的
这是执行:
如果你不明白,给我写评论:)
多亏了@Jared Smith分享的文章,我才明白这一点
这个问题是由python如何处理默认参数引起的。从文章中:
我的
memo
字典每次调用都会发生变异。因此,我只是更改了memo=None
,并添加了一个检查,以查看它是否是函数的第一次调用:相关问题 更多 >
编程相关推荐