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

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 之前重新启动备忘录，我不想像这样手动执行：print(coinChange([2], 3, memo = {})).

Answer 1

由于以下原因，您提到的问题未与您共享的代码一起给出

x = coinChange(coins, amount - coin, minimum - 1, 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 = {}
    ...

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

Wrong result if a recursive function is called twice successively with different parameters

python

recursion

caching

dynamic-programming

memo