class Solution(object): def numSquares(self, n): """ :type n: int :rtype: int """ maxValue=2**31-1 ref=[maxValue]*(n+1) ref=0 for i in range(1, n+1): if math.sqrt(i)==int(math.sqrt(i)): ref[i]=1 else: j=1 while j**2 < i: ref[i]=min(ref[i], ref[i-j**2]+1) j+=1 return ref[-1]
I got the same problem. After testing a 40K number, the python needs 2.2s. This is indeed slow.
I guess this is because every variable in python is an object, and the time and space efficiency of doing this is not high.