```
def numSquares(self, n):
#print "numSquares, n = ", n
squareNumbers = []
i = 1
dpMatrix = [0 for i in range(n+1)]
j = 0
squareNumbers = [1]
for i in range(1, n+1):
#print "i = ", i, " dpMatrix = ", dpMatrix
while j*j <= i:
squareNumbers.append(j*j)
j += 1
#print "squareNumbers = ", squareNumbers, " squareNumbers[-1] = ", squareNumbers[-1]
if (i % squareNumbers[-1]) == 0:
#print "1 i = ", i, " squareNumbers[-1] = ", squareNumbers[-1], " i % squareNumbers[-1] = ", i % squareNumbers[-1]
dpMatrix[i] = (i/squareNumbers[-1])
else:
#maximum is i
n0 = i
n4 = []
for sq in squareNumbers[::-1]:
#print "sq = ", sq
if sq > 0 and i % sq == 0:
n0 = i / sq
break
else:
div1 = i / sq
rem1 = i % sq
n4.append(div1+dpMatrix[rem1])
#print "n0 = ", n0, "n4 = ", n4
minN4 = min(n4)
#print "2 i = ", i
n1 = dpMatrix[i-1] + 1
#print "n1 = ", n1
b1 = i / squareNumbers[-1]
remaining = i % squareNumbers[-1]
n2 = dpMatrix[remaining] + b1
#print "b1 = ", b1, " remining = ", remaining, " dpMatrix[remaining] = ", dpMatrix[remaining], " n2 = ", n2
dpMatrix[i] = min(n0, n1, n2, minN4)
#print "2 dpMatrix = ", dpMatrix
#print "in the end, dpMatrix = ", dpMatrix
return dpMatrix[-1]
```