为什么我的备忘录对象打印所有组合?

Question

我找到了数组中最短的数字组合，等于目标和:

def bestSum(targetSum, numbers, memo = None):
if memo is None:
memo = {}
if targetSum in memo:
return memo[targetSum]
if targetSum == 0:
return []
if targetSum < 0:
return None
shortestCombination = None
for n in numbers:
remainder = targetSum - n
remainderCombination = bestSum(remainder, numbers, memo)
if remainderCombination is not None:
remainderCombination.append(n)
combination = remainderCombination
# if the combination is shorter than the shortest, update it
if shortestCombination is None or len(combination) < len(shortestCombination):
shortestCombination = combination
memo[targetSum] = shortestCombination
return shortestCombination
print(bestSum(100, [1, 2, 5, 25]))   # [25, 25, 25, 25]
print(bestSum(7, [5, 3, 4, 7]))  # 7
print(bestSum(8, [2, 3, 5]))  # [3, 5]
print(bestSum(8, [1, 4, 5]))  # [4, 4]

暴力破解可以工作，但对于记忆解决方案，只有第二和第三个答案匹配(例如#7和#[5,3])。我好像修不了。

Answer 1

您正在修改您在memo中存储的列表，从而破坏了memo。如果您只是在修改列表之前复制返回的列表，那么您的代码可以正常工作:

def bestSum(targetSum, numbers, memo = None):
if memo is None:
memo = {}
if targetSum in memo:
return memo[targetSum]
if targetSum == 0:
return []
if targetSum < 0:
return None
shortestCombination = None
for n in numbers:
remainder = targetSum - n
combination = bestSum(remainder, numbers, memo)
if combination is not None:
combination = combination + [n]
if shortestCombination is None or len(combination) < len(shortestCombination):
shortestCombination = combination
if shortestCombination:
memo[targetSum] = shortestCombination
return shortestCombination
print(bestSum(100, [1, 2, 5, 25]))   # [25, 25, 25, 25]
print(bestSum(7, [5, 3, 4, 7]))  # 7
print(bestSum(8, [2, 3, 5]))  # [3, 5]
print(bestSum(8, [1, 4, 5]))  # [4, 4]