I am following the dynamic programming tutorial by freeCodeCamp.org on youtube here. When he performs memoization, he says that the memo object gets passed by reference. I have consulted google and understand that when python passes lists and dictionaries they behave as "pass by references" as well.
So this works fine for the fibonacci sequence example and the outputs are as expected:
def fib(n, memo = {}):
if n <= 2: return 1
if n in memo: return memo[n]
memo[n] = fib(n-2, memo) + fib(n-1, memo)
return memo[n]
print(fib(6)) # outputs 8 as expected
print(fib(7)) # outputs 13 as expected
print(fib(8)) # outputs 21 as expected
print(fib(50)) # outputs 12586269025 as expected
However, for a more advanced example later in the tutorial, howSum, running the test cases all at once will mess up the results. It looks like the memo dict or the numbers list is keeping values from previous cases. The howSum function is suppoed to return a list of numbers from numbers that sum up to targetSum.
def howSum(targetSum, numbers, memo = {}):
if targetSum == 0: return []
elif targetSum < 0: return None
elif targetSum in memo: return memo[targetSum]
for num in numbers:
remainder = targetSum - num
result = howSum(remainder, numbers, memo)
if result is not None:
memo[targetSum] = [num] + result
return memo[targetSum]
memo[targetSum] = None
return None
print(howSum(7,[2,3])) # outputs [2, 2, 3] as expected
print(howSum(7,[5,3,4,7])) # outputs [2, 2, 3] but correct answer should be [3,4]
print(howSum(7,[2,4])) # outputs [2, 2, 3] but it should output None
print(howSum(8,[2,3,5])) # outputs [2, 2, 2, 2] as expected
print(howSum(300,[7,14])) # outputs a long array of 7s and 2s that sum to 300, but it should output None
Can anyone explain this please? And how do I avoid this issue? Thank you.
