# A/C Python solution, DP, easy to understand, beat 11%

• ``````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]``````

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