why doesn't memoization work in this Python code?

user_14849198 0
Viewed 299

i am following a dynamic programming video. However the memoization for my code is not working. It is not storing any True/False when i print(memo) it is blank. Please advise

def cansum(targetsum,numbers):
      memo = dict()
      print(memo)
      # check in memory
      if targetsum in memo:
            return memo[targetsum]
      if targetsum < 0: return False
      if targetsum == 0: return True
      for number in numbers:
            remainder = targetsum - number
            if cansum(remainder,numbers) == True:
                  memo[targetsum] = True
                  return True
      memo[targetsum] = False
      return False


print(cansum(7,[2,3])) #True
print(cansum(7,[5,3,4,7])) #True
memoization python
1 Answers

I think this is what you might want to do:

def cansum(targetsum, numbers):
    memo = dict()

    def cansum_helper(targetsum, numbers):
        # check in memory
        if targetsum in memo:
            return memo[targetsum]
        if targetsum < 0:
            return False
        if targetsum == 0:
            return True
        for number in numbers:
            remainder = targetsum - number
            if cansum_helper(remainder, numbers) == True:
                memo[targetsum] = True
                return True
        memo[targetsum] = False
        return False

    result = cansum_helper(targetsum, numbers)

    print(memo)

    return result


print(cansum(7, [2, 3]))  # True
print(cansum(7, [5, 3, 4, 7]))  # True

If you put

memo = dict()

into recursive function, you are creating one dict for every recursive function, and once the memo is set, the return statement follows, so you won't be able to see changes. But what is intended is that you only need one dict for your whole function.

user_75234000
Related