# Regarded correct python solution with TLE

• ``````def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
if n < 4:
return n
if n == 4:
return 1
res = dict()
res[0] = 0
res[1] = 1
res[2] = 2
res[3] = 3
res[4] = 1

for i in range(5,n+1):
res[i] = sys.maxint
j = 1
while j*j <= i:
if j*j == i:
res[i] = 1
else:
res[i] = min(res[i], 1+res[i-j*j])
j += 1
return res[n]
``````

I think my python solution is correct. And some test cases can be passed through "Custom TestCase", but not through submission. I am really confused....

• If using Python, you need to turn the array "res" as static, the code below is for your reference.

``````class Solution(object):
cache = [0] * 10001

for i in range(1, 101):
cache[i**2] = 1

def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
# DP
# r = [0] * (n+1)
# for i in range(1, int(n**0.5)+1):
#     r[i**2] = 1

for i in range(2, n+1):
tmp = 10000
if self.cache[i] != 0:
continue
for j in range(1, int(i ** 0.5) + 1) :
idx = i - j**2
# print idx, "i", r[idx]
tmp = tmp if tmp < self.cache[idx] else self.cache[idx]
self.cache[i] = tmp + 1

return self.cache[n]``````

• I see. Thanks for your help.

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