# Why is Python DP solution TLE

• I made these two lists static however still TLE

``````   class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
self.dp = [i for i in range(n+1)]
self.squares = [i*i for i in range(1, int(n**0.5) + 1)]

for i in range(1, n+1):
for sq in self.squares:
if i - sq < 0:
break
self.dp[i] = min(self.dp[i], self.dp[i - sq] + 1)

return self.dp[-1]``````

• Good question. The same solution in Java beats 91%.

• I tried with DP algorithm but get very poor performance (5%), the same algorithm beats 99% in "Ugly Number II" which is a quite similar problem.

• My code is about twice speed as yours, but stil TLE, sigh

``````    def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
if math.sqrt(n) == int(math.sqrt(n)):
return 1

l = map(lambda i : i*i, [i for i in range(1, int(math.sqrt(n)))])
f = [ 0 for i in range(n+1) ]

i = 1
while i < n+1:
f[i] = min([ f[i-j] for j in l if i - j >= 0 ]) + 1
i += 1

return f[n]
``````

• Because Python is slow, which forces you to find a better algorithm. Or, you can use other languages to AC.

• Initializing self.dp and self.squares are actually O(n), while n can be very large.

• @zkh1991 I have the same question

• @zkh1991 Replace the if statement by if i < sq

• @zkh1991
DP solution can be accepted, my code is 99% the same as your but only process a corner case at the very beginning , not very good performance but still beats 1/3 of the solutions on average:

``````    if n == int(n**0.5):
return 1
dp = [i for i in xrange(n+1)]
square = [i**2 for i in xrange(int(n**0.5)+1)]
for i in xrange(1,n+1):
for item in square:
if i-item<0:
break
else:
dp[i] = min(dp[i],dp[i-item]+1)
return dp[n]
``````

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