I have this recursive function:
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
When I print this:
print(coinChange([2], 3)) #-1
It shows -1
, which is correct.
But, when I print this:
print(coinChange([1,2,5], 11)) #3 print(coinChange([2], 3)) #the correct answer is -1 but it's showing 2
It shows 3
then 2
.
As you can see, the result of print(coinChange([2], 3))
weirdly changed from -1
to 2
.
The memo
is the reason for causing that wrong answer. But I don’t know how to update the function so that memo is re-initiated before each first call of coinChange
, and I don’t want to do it manually like this: print(coinChange([2], 3, memo = {}))
.
Advertisement
Answer
The issue you mention isn’t given with the code you share because of the following
x = coinChange(coins, amount - coin, minimum - 1, memo={})
To use your memo, you need pass it to the recursive calls
x = coinChange(coins, amount - coin, minimum - 1, memo=memo)
Effectivly you shouldn’t use a mutable object as default variable, because multiple calls will share the same instance, the issue is to use a None
def coinChange(coins, amount: int, minimum=float('inf'), memo=None) -> int: if memo is None: memo = {} ...