I've seen that the dp solution is not accepted in Python. Some use static *dp* in order to use it. And we can also solve it using number theory knowledge. But **what if in a competition we don't know that theory? What if we are not allowed to use static dp?** Here is an accepted solution using BFS:

```
class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
q1 = [0]
q2 = []
level = 0
visited = [False] * (n+1)
while True:
level += 1
for v in q1:
i = 0
while True:
i += 1
t = v + i * i
if t == n: return level
if t > n: break
if visited[t]: continue
q2.append(t)
visited[t] = True
q1 = q2
q2 = []
return 0
```