Python 的行为方式很奇怪（动态编程）[重复]

Question

我编写了以下代码，它采用整数 N 和整数数组：arr。任务是找到 arr 中总和为 N 的整数的最短组合。 arr 的每个元素都可以根据需要使用多次。例如 9, [3,2] 应产生结果 [3,3,3] 而不是 [2,2,2,3]，因为前一个组合的长度较短（元素数量较少） ).

def bestSum(n, arr, memo={}):
    key=str(n)
    if key in memo.keys():
        return memo[key]
    if n<0 :
        return None
    if n==0:
        return []

    best_solution = None
    for i in arr:
        solution= bestSum(n-i,arr,memo)
        if (solution is not None):
            combination = list(k for k in solution)
            combination.append(i)
            if((best_solution is None ) or (len(combination)<len(best_solution))):
                best_solution=combination
    memo[key] =best_solution
    return best_solution



print(bestSum(8,[3,2]))
print(bestSum(8, [4,2]))

第一个打印语句的输出是 [2,3,3]，这是正确的。 但是第二个 print 语句也产生了 [2, 3, 3]，这是不可能的，因为在这种情况下 arr 中没有 3。输出应该是 [4,4]

现在，如果我删除第一个语句并仅执行第二个语句，那么它会产生正确的结果 => [4,4]

再次，如果我改变顺序 -

print(bestSum(8, [4,2]))
print(bestSum(8,[3,2]))

这两个都会产生 [4,4]

即使在完成将值返回到第一个print之后，在

 print(bestSum(8, [4,2]))

中创建的memo似乎仍然存在，并且第二个调用

 print(bestSum(8, [3,2]))

正在使用相同的memo。

我不明白为什么会这样？完成第一个 print 后，第一个 memo 对象不应该自动删除吗？难道不应该在第二次调用中创建一个新的memo吗？

如果 memo 在第一个语句完成后继续存在，它应该能够在该语句之外访问，例如

print(memo)

但事实并非如此

Answer 1

在Python中，默认参数是在定义函数时计算的，而不是每次调用函数时计算的。这意味着，如果您使用可变的默认参数并对其进行变异，则每当调用该函数时都会使用变异的对象。

因此，在您的函数中，

memo={}

仅在定义函数时计算一次。这就是为什么当您第二次调用

bestSum

时，它使用与第一次调用相同的

memo

字典，而不是新的空字典。这就是第二次调用返回错误结果的原因，因为它正在利用第一次调用中的

memo

。

避免此问题的常见 Python 习惯用法是使用

None

作为默认参数值，然后在函数内设置实际的默认值。以下是修改函数的方法：

def bestSum(n, arr, memo=None):
    if memo is None:
        memo = {}
    key=str(n)
    if key in memo.keys():
        return memo[key]
    if n<0 :
        return None
    if n==0:
        return []

    best_solution = None
    for i in arr:
        solution= bestSum(n-i,arr,memo)
        if (solution is not None):
            combination = list(k for k in solution)
            combination.append(i)
            if((best_solution is None ) or (len(combination)<len(best_solution))):
                best_solution=combination
    memo[key] =best_solution
    return best_solution

通过此更改，每次调用

bestSum

时，如果未提供其他值，

memo

将是一个新的空字典，因此您不会遇到影响结果的先前调用的数据问题。

---

话虽如此，这里还有一个更Pythonic的解决方案：