The idea is to generate a directed graph with the root as the target number, the other node as the current values during subtraction and edge has the value of the square number that has been subtracted from the previous node.

Use a hash table to store the graph.

Do the BFS starting from the root recording the depth, when the visited node has value 0, return the depth.

```
from collections import deque
import numpy as np
class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
graph = {}
for i in range(n,0,-1):
sqrts = np.array(range(1, int(np.sqrt(i)) + 1))
sqaures = sqrts * sqrts
graph[i] = np.array([i] * len(sqaures)) - sqaures
q = deque([(n,0)])
s = set([n])
while q:
current = q.popleft()
num, depth = current
if num == 0:
return depth
for child in graph[num]:
if child not in s:
q.append((child, depth+1))
s.add(child)
```