# 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关键在于定义状态和找到转化关系。这里用dp\[i]代表对`i`的perfect squares count，转化关系并不是很直观:

```
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`

Source: [https://leetcode.com/problems/perfect-squares/discuss/71495/An-easy-understanding-DP-solution-in-Java](https://leetcode.com/problems/perfect-squares/discuss/71495/An-easy-understanding-DP-solution-in-Java)

关于DP，这题的特点是 （by @mnmunknown）：

* 要凑出来一个和正好是 n 的选择组合；
* 能选的元素是固定数量的 perfect square (有的会超) ；
* 一个元素可以选多次；

说明这其实是个背包问题。

### Mathematical

See \[\[\[\[\[[https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem)\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem))\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem)\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem)))\](https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem%29\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem%29%29\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem%29\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem\]%28https://en.wikipedia.org/wiki/Lagrange's\_four-square\_theorem%29%29%29)\\](https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem\)]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem\)\)]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem\)]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem\)\)\)]\(https://en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem\)]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem\)\)]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem\)]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem]\(https:/en.wikipedia.org/wiki/Lagrange's_four-square_theorem\)\)\)\)/))

### BFS

用BFS乍一看较难理解，其实在于问题转化：

把数字0, 1, ..., n看成一个图graph的节点node，节点i, j 连接的条件是

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

已知起始点`0`,和终点`n`，这样问题就转化为一个最短路径问题。故使用BFS。

> ```
> // 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)

```java
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

```java
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)

```java
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)

```java
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%)

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

        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.add(0);
        visited.add(0);

        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);
                        visited.add(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://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](https://mnmunknown.gitbooks.io/algorithm-notes/82ff0c_bei_bao_wen_ti.html)
