class Solution(object):
numSquaresDP = [0]
def numSquares(self, n):
if len(self.numSquaresDP) <= n:
perfectSqr = [v**2 for v in xrange(1, int(math.sqrt(n)) + 1)]
for i in xrange(len(self.numSquaresDP), n + 1):
self.numSquaresDP.append( min(1 + self.numSquaresDP[i  sqr] for sqr in perfectSqr if sqr <= i))
return self.numSquaresDP[n]
5 lines Python static DP ( 160ms )


My solution with the exact same answer other than the DP array(
numSquareDP
) being inside the function exceeds the time limit, which is understandable as you are reusing the DP array for all the tests, which can improve the runtime significantly if there are many test, which there are, all 600 of them. Therefore, I'm not sure it this approach is valid.