Accepted recursive solution in Python using memoization


  • 0
    R
    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]
            else:
                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
    M

    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.