我正在学习有关动态编程的教程,并且正在努力在以下问题中实现记忆化:
*写一个函数叫canSum(targetSum, numbers)
返回True
仅当数组中的数字之和达到目标总和时。数组中的所有数字都是正整数,您可以多次使用它们来求解。
Example:
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