0

我正在尝试获取一个包含产生目标总和的最少值的列表。如果没有找到值，我们需要返回 None。最初我尝试不使用存储中间结果以降低时间复杂度的 memo 变量。我得到了一个带有 values 的列表[4,4]，这是正确的，但是在添加备忘录之后，我得到了一个带有 values 的列表[4, 1, 4]，这是不正确的。我是 Python 新手。有人可以指出错误吗？

def bestSum(targetSum,numbers,memo={}):
    if targetSum in memo.keys():
        return memo[targetSum]
    if targetSum == 0:
        return []
    if targetSum<0:
        return None
    myShortestCombination = None
    for num in numbers:
        remainder = targetSum - num
        reamainderCombination = bestSum(remainder,numbers,memo)
        if reamainderCombination != None:
            reamainderCombination.append(num)
            combination = reamainderCombination
            if (myShortestCombination == None) or (len(combination) < len(myShortestCombination)):
                myShortestCombination = combination
    memo[targetSum] = myShortestCombination
    return myShortestCombination


print(bestSum(8,[1,4,5],memo={}))
print(bestSum(100,[1,2,5,25],memo={}))
4

0 回答 0