Given a positive integern, find the least number of perfect square numbers (for example,`1, 4, 9, 16, ...`

) which sum ton.Example 1:Input:n=`12`

Output:3Explanation:`12 = 4 + 4 + 4.`

This problem can be solved in three ways: Dynamic Programming, BFS, and Math. Applying Dynamic Programming is less efficient as BFS, since it unnecessarily explores the non-least number of perfect square numbers. Moreover, according to Lagrange’s four-square theorem, with BFS we would be able to find the answer within at most four iterations. Let’s take a look at each approach now.

### Dynamic programming

#### Bottom up

Initialise an array `dp[]`

with length equals to `n+1`

, and set `dp[0] = 0`

. Iterating from `1`

to `n`

, `dp[i]`

is the least number of perfect square numbers summed to `n`

. So we can have the transition function as:

dp[i] = min(dp[i-square] if i-square>=0), square refers to square numbers

```
class Solution:
def numSquares(self, n: int) -> int:
dp = [float('inf')] * (n+1)
dp[0] = 0
for i in range(1,n+1):
for j in range(1,int(i**0.5)+1):
if i-j**2 >= 0:
dp[i] = min(dp[i],dp[i-j**2]+1)
else:
break
return dp[-1]
```

#### Top down

Starting from `n`

, we define a recursive function `helper(node)`

which returns the least number of square numbers summed to `node`

, and the exit condition is when `node`

itself is a square number, we could simply `return 1`

.

```
class Solution:
def numSquares(self, n: int) -> int:
opts = set([])
for i in range(1,n+1):
if i ** 2 > n:
break
opts.add(i**2)
dic = {}
def helper(node=n):
if node in opts:
return 1
else:
if node not in dic:
ret = float('inf')
for opt in opts:
if node - opt > 0:
ret = min(ret,helper(node-opt)+1)
dic[node] = ret
return dic[node]
return helper()
```

Or in Python, we could use @lru_cache(None) from `functools`

package.

```
class Solution:
def numSquares(self, n: int) -> int:
opts = set([])
for i in range(1,n+1):
if i ** 2 > n:
break
opts.add(i**2)
@lru_cache(None)
def helper(node=n):
if node in opts:
return 1
else:
ret = float('inf')
for opt in opts:
if node - opt > 0:
ret = min(ret,helper(node-opt)+1)
return ret
return helper()
```

### Breadth first search

#### From n to square numbers

Treating each number as a node, two nodes are connected when the difference between them is a square number. Therefore we can apply BFS to this tree, rooted as `n`

.

Notably, to avoid repeated computations, we can implement a hashset to record the visited numbers.

```
class Solution:
def numSquares(self, n: int) -> int:
i = 1
opts = []
while i**2 <= n:
opts.append(i**2)
i += 1
queue = collections.deque()
queue.append((n,0))
# avoid repeated computations for visited node
visited = set([])
while queue:
num,step = queue.popleft()
if num in visited:
continue
visited.add(num)
for opt in opts:
if num == opt:
return step + 1
if num-opt < 0:
break
queue.append((num-opt,step+1))
```

Or, another way of BFS:

```
class Solution:
def numSquares(self, n: int) -> int:
i = 1
opts = []
while i**2 <= n:
opts.append(i**2)
i += 1
# initialised as a hashset
# avoid repeated computations for visited node
q = {n}
step = 0
while q:
step += 1
new_q = set([])
for num in q:
for opt in opts:
if num == opt:
return step
if num-opt < 0:
break
new_q.add(num-opt)
q = new_q
return step
```

#### From square numbers to n

Similarly, we would treat this as a tree, but start with square numbers this time. Exit condition is when we find the target `n`

.

```
class Solution:
def numSquares(self, n: int) -> int:
q = []
opts = []
for i in range(1,n+1):
if i ** 2 > n:
break
opts.append(i**2)
q.append(i**2)
if opts[-1] == n:
return 1
step = 1
visited = set([])
while q:
size = len(q)
step += 1
for i in range(size):
num = q.pop(0)
for opt in opts:
if num + opt == n:
return step
elif num + opt < n and num+opt not in visited:
visited.add(num+opt)
q.append(num+opt)
elif num + opt > n:
break
```

## Math

If you are interested in solving it mathematically, feel free to check this Leetcode Discuss. This approach is, as mentioned, based on Lagrange’s four-square theorem.