使用不同的参数连续调用递归函数两次，结果错误

Question

我有这个递归函数:

def coinChange(coins, amount: int, minimum = float('inf'), memo={}) -> int:
if amount in memo: return memo[amount]
if amount < 0: return -1
if amount == 0: return 0
for coin in coins:
x = coinChange(coins, amount - coin, minimum - 1, memo)
minimum = min(x, minimum) if x != -1 else minimum
if minimum == 0: break
memo[amount] = -1 if minimum == float('inf') else minimum + 1
return -1 if minimum == float('inf') else minimum + 1

当我打印这个时:

print(coinChange([2], 3)) #-1

显示-1，正确。但是，当我打印这个时:

print(coinChange([1,2,5], 11)) #3
print(coinChange([2], 3)) #the correct answer is -1 but it's showing 2

先显示3，后显示2。可以看到，print(coinChange([2], 3))的结果奇怪地从-1变成了2。

memo是导致错误答案的原因。但是我不知道如何更新函数，以便在每次第一次调用coinChange之前重新启动memo，我不想这样手动执行:print(coinChange([2], 3, memo = {})).

Answer 1

由于以下原因，您提到的问题与您共享的代码无关

x = coinChange(coins, amount - coin, minimum - 1, memo={})

要使用memo，需要将其传递给递归调用

x = coinChange(coins, amount - coin, minimum - 1, memo=memo)

---

实际上你不应该使用可变对象作为默认变量，因为多个调用将共享同一个实例，问题是使用None

def coinChange(coins, amount: int, minimum=float('inf'), memo=None) -> int:
if memo is None:
memo = {}
...