CODEWITHSUNDEEP
pythonmemoization
SoraHeart
SoraHeart

Reputation: 420

why doesn't memoization work in this Python code?

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

Upvotes: 2

Views: 462

Answers (1)

SiAce
SiAce

Reputation: 391

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.

Upvotes: 2

Related Questions