# Perfect Squares

#math #dynamicprogramming

Given a positive integer n, find the least number of perfect square numbers (for example,`1, 4, 9, 16, ...`) which sum to n.

Example 1:

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

Example 2:

``````Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.``````

## Analysis

### Dynamic Programming

``dp[n] = Min{ dp[n - i*i] + 1 }, for n - i*i >=0 && i >= 1``

The most intuitive approach besides brute force would probably be dynamic programming, whether it's bottom up iteration or recursion with memoization, they all based on the recurrence relation:

``````dp[0] = 0
dp[1] = dp[0]+1 = 1
dp[2] = dp[1]+1 = 2
dp[3] = dp[2]+1 = 3
dp[4] = Min{ dp[4-1*1]+1, dp[4-2*2]+1 }
= Min{ dp[3]+1, dp[0]+1 }
= 1
dp[5] = Min{ dp[5-1*1]+1, dp[5-2*2]+1 }
= Min{ dp[4]+1, dp[1]+1 }
= 2
.
.
.
dp[13] = Min{ dp[13-1*1]+1, dp[13-2*2]+1, dp[13-3*3]+1 }
= Min{ dp[12]+1, dp[9]+1, dp[4]+1 }
= 2
.
.
.
dp[n] = Min{ dp[n - i*i] + 1 },  for n - i*i >=0 && i >= 1``````

where `dp[n]` stands for the perfect squares count of the given `n`

• 要凑出来一个和正好是 n 的选择组合；

• 能选的元素是固定数量的 perfect square (有的会超) ；

• 一个元素可以选多次；

### BFS

`j = i + (a perfect square number)` or `i = j + (a perfect square number)`

``````// Consider a graph which consists of number 0, 1,...,n as
// its nodes. Node j is connected to node i via an edge if
// and only if either j = i + (a perfect square number) or
// i = j + (a perfect square number). Starting from node 0,
// do the breadth-first search. If we reach node n at step
// m, then the least number of perfect square numbers which
// sum to n is m. Here since we have already obtained the
// perfect square numbers, we have actually finished the
// search at step 1.``````

## Solution

Dynamic Programming - Iterative Bottom Up (~ 22ms AC)

``````class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
}``````

DP another version

``````class Solution {
public int numSquares(int n) {

int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 1; i <= n; ++i) {
int min = Integer.MAX_VALUE;
int j = 1;
while(i - j*j >= 0) {
min = Math.min(min, dp[i - j*j] + 1);
j++;
}

dp[i] = min;
}
return dp[n];

}
}``````

Mathematical - (1ms AC)

``````class Solution {
// Based on Lagrange's Four Square theorem, there
// are only 4 possible results: 1, 2, 3, 4.
public int numSquares(int n)
{
// If n is a perfect square, return 1.
if(is_square(n))
{
return 1;
}

// The result is 4 if and only if n can be written in the
// form of 4^k*(8*m + 7). Please refer to
// Legendre's three-square theorem.
while ((n & 3) == 0) // n%4 == 0
{
n >>= 2;
}
if ((n & 7) == 7) // n%8 == 7
{
return 4;
}

// Check whether 2 is the result.
int sqrt_n = (int)(Math.sqrt(n));
for(int i = 1; i <= sqrt_n; i++)
{
if (is_square(n - i*i))
{
return 2;
}
}

return 3;
}

private boolean is_square(int num)
{
int sqrt_num = (int) Math.sqrt(num);
return sqrt_num * sqrt_num == num;
}
}``````

Recursion Memoization (NOT RECOMMENDED) - (655ms AC 4.86% percentile)

``````class Solution {
public int fun(Map<Integer,Integer> map, int target)
{
if(map.containsKey(target))
return map.get(target);
int temp = Integer.MAX_VALUE;
for(int i = 1; i<= (int)Math.sqrt(target); i++)
{
temp = Math.min(temp, fun(map,target - i*i)+1);
}
map.put(target, temp);
return temp;
}
public int numSquares(int n) {
int nums = (int)Math.sqrt(n);
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 1; i<= (int)Math.sqrt(n); i++)
{
map.put(i*i,1);
}
return fun(map,n);

}``````

BFS Version (~113ms 21.89%)

``````class Solution {
public int numSquares(int n) {
int numOfSquares = 0;

Set<Integer> visited = new HashSet<>();

while (!queue.isEmpty()) {
int size = queue.size();
numOfSquares++;
while (size > 0) {
int num = queue.poll();
for (int i = 1; i*i <= n; i++) {
int x = num + i*i;
if (x == n) {
return numOfSquares;
}
if (x > n) {
break;
}
if (!visited.contains(x)) {
queue.offer(x);
}
}
size--;
}
}
return numOfSquares;
}
}``````

## Reference

https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-(BFS-DP-static-DP-and-mathematics

https://mnmunknown.gitbooks.io/algorithm-notes/82ff0c_bei_bao_wen_ti.html

Last updated