Accepted recursive solution in Python using memoization

  • 0
    import math
    cache = {}  # dict to cache the result
    class Solution:
        global cache
        def r(self, n):
            return range(1, int(math.sqrt(n))+1)    
            # helper function which returns a list [1 to sqrt(n)]
        def numSquares(self, i):
            if i == 0:
                return 0
            if i < 0:
                return 01e100  #No solution is possible 
            if i in cache:
                return cache[i]
                answer = 1 + min([self.numSquares(i - cj * cj) for cj in self.r(i)]) 
                #return min(f(S-1), f(S-4), S(S-9).....)
                cache[i] = answer
            return answer

  • 0

    not accepted

    Line 6: RuntimeError: maximum recursion depth exceeded while calling a Python object

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.